Submission #2559153

---

Source Code Expand

// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int N, Q;
 
signed main() {
    cin >> N >> Q;

    int L = 2*N;
    vector<int> A(L), B(L);
    for(int i=0; i<L; i++) cin >> A[i];
    for(int i=0; i<L; i++) cin >> B[i];

    int sum = 0, use = 0;
    set< pair<int, int> > S;
    for(int i=1; i<L-1; i++) {
        sum += max(A[i], B[i]);
        if(A[i] < B[i]) use ^= 1;
        S.insert(make_pair(abs(A[i] - B[i]), i));
    }

    while(Q--) {
        int i, x, y; cin >> i >> x >> y; i--;
        if(i != 0 && i != L-1) {
            sum -= max(A[i], B[i]);
            if(A[i] < B[i]) use ^= 1;
            S.erase(make_pair(abs(A[i] - B[i]), i));

            sum += max(x, y);
            if(x < y) use ^= 1;
            S.insert(make_pair(abs(x - y), i));
        }

        A[i] = x, B[i] = y;
        int ans = sum + A[0] + A[L-1];
        if(use) ans -= S.begin() -> first;
        cout << ans << endl;
    }
    return 0;
}

Submission Info

Judge Result