Submission #2105687


Source Code Expand

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int n, q;
    cin >> n >> q;
    n *= 2;
    VL a(n), b(n);
    REP(i,n) scanf("%lld", &a[i]);
    REP(i,n) scanf("%lld", &b[i]);

    ll suma = 0;
    REP(i,n) suma += a[i];

    multiset<ll> st;
    ll pos = 0;
    int c = 0;
    FOR(i,1,n-2){
        st.insert(b[i] - a[i]);
        if (b[i] > a[i]){
            pos += b[i] - a[i];
            c++;
        }
    }

    while (q--){
        int i;
        ll x, y;
        scanf("%d %lld %lld", &i, &x, &y);
        i--;
        if (i == 0 || i == n-1){
            suma += x - a[i];
        }else{
            suma += x - a[i];
            ll od = b[i] - a[i];
            ll nw = y - x;
            st.erase(st.find(od));
            st.insert(nw);
            if (od > 0){
                c--;
                pos -= od;
            }
            if (nw > 0){
                c++;
                pos += nw;
            }
        }
        a[i] = x;
        b[i] = y;

        // cout << "suma " << suma << endl;
        // cout << "c " << c << "  sumpos " << pos << endl;
        // for (ll x : st) cout << x << " ";
        // cout << endl;

        ll ans = suma;
        if (c % 2 == 0){
            ans += pos;
        }else{
            ll p, q;
            auto itr = st.upper_bound(0);
            p = *itr;
            itr--;
            q = *itr;
            ans += max(pos - p, pos + q);
        }
        printf("%lld\n", ans);
    }

    return 0;
}

Submission Info

Submission Time
Task C - Paired Parentheses
User TangentDay
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2141 Byte
Status AC
Exec Time 256 ms
Memory 14208 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:35:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     REP(i,n) scanf("%lld", &a[i]);
                                  ^
./Main.cpp:36:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     REP(i,n) scanf("%lld", &b[i]);
                                  ^
./Main.cpp:55:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld %lld", &i, &x, &y);
                                          ^

Judge Result

Set Name Sample Subtask1 Subtask2 All
Score / Max Score 0 / 0 200 / 200 300 / 300 200 / 200
Status
AC × 2
AC × 14
AC × 15
AC × 43
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
Subtask1 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt
Subtask2 s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt
All 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s3_29.txt, s3_30.txt, s3_31.txt, s3_32.txt, s3_33.txt, s3_34.txt, s3_35.txt, s3_36.txt, s3_37.txt, s3_38.txt, s3_39.txt, s3_40.txt, s3_41.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
s1_01.txt AC 1 ms 256 KB
s1_02.txt AC 1 ms 256 KB
s1_03.txt AC 1 ms 256 KB
s1_04.txt AC 1 ms 256 KB
s1_05.txt AC 1 ms 256 KB
s1_06.txt AC 1 ms 256 KB
s1_07.txt AC 1 ms 256 KB
s1_08.txt AC 1 ms 256 KB
s1_09.txt AC 1 ms 256 KB
s1_10.txt AC 1 ms 256 KB
s1_11.txt AC 1 ms 256 KB
s1_12.txt AC 1 ms 256 KB
s1_13.txt AC 1 ms 256 KB
s2_14.txt AC 5 ms 768 KB
s2_15.txt AC 5 ms 896 KB
s2_16.txt AC 75 ms 8832 KB
s2_17.txt AC 61 ms 7424 KB
s2_18.txt AC 117 ms 12800 KB
s2_19.txt AC 114 ms 12800 KB
s2_20.txt AC 114 ms 12800 KB
s2_21.txt AC 114 ms 12800 KB
s2_22.txt AC 5 ms 768 KB
s2_23.txt AC 5 ms 896 KB
s2_24.txt AC 5 ms 768 KB
s2_25.txt AC 118 ms 12800 KB
s2_26.txt AC 118 ms 12800 KB
s2_27.txt AC 118 ms 12800 KB
s2_28.txt AC 117 ms 12800 KB
s3_29.txt AC 88 ms 7040 KB
s3_30.txt AC 104 ms 4480 KB
s3_31.txt AC 93 ms 10240 KB
s3_32.txt AC 217 ms 11136 KB
s3_33.txt AC 88 ms 7040 KB
s3_34.txt AC 256 ms 14208 KB
s3_35.txt AC 250 ms 14208 KB
s3_36.txt AC 193 ms 14208 KB
s3_37.txt AC 195 ms 14208 KB
s3_38.txt AC 200 ms 14208 KB
s3_39.txt AC 198 ms 14208 KB
s3_40.txt AC 41 ms 1024 KB
s3_41.txt AC 40 ms 1024 KB