Submission #3128484


Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;

int main()
{
	int n, q;
  cin>>n>>q;
  ll a[200001], b[200001];
  for(int i=1; i<=2*n; i++){
    cin>>a[i];
  }
  for(int i=1; i<=2*n; i++){
    cin>>b[i];
  }
  multiset<ll> st;
  ll ans=a[1]+a[2*n];
  int ct0=0, ct1=0;
  for(int i=2; i<2*n; i++){
    if(b[i]>a[i]){
      ct1++;
    }else if(b[i]==a[i]){
      ct0++;
    }
    st.insert(abs(b[i]-a[i]));
    ans+=max(a[i], b[i]);
  }
  for(int i=0; i<q; i++){
    int p; ll x, y;
    cin>>p>>x>>y;
    if(p==1 || p==2*n){
      ans=ans-a[p]+x;
      a[p]=x; b[p]=y;
    }else{
      if(b[p]>a[p]){
        ct1--;
      }else if(b[p]==a[p]){
        ct0--;
      }
      st.erase(st.lower_bound(abs(b[p]-a[p])));
      ans=ans-max(a[p], b[p])+max(x, y);
      a[p]=x; b[p]=y;
      st.insert(abs(y-x));
      if(y>x){
        ct1++;
      }else if(y==x){
        ct0++;
      }
    }
    if(ct0>0 || ct1%2==0){
      cout<<ans<<endl;
    }else{
      cout<<ans-*(st.begin())<<endl;
    }
  }
	return 0;
}

Submission Info

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

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 2304 KB
s1_02.txt AC 2 ms 2304 KB
s1_03.txt AC 1 ms 2304 KB
s1_04.txt AC 1 ms 2304 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 2304 KB
s1_10.txt AC 2 ms 2304 KB
s1_11.txt AC 1 ms 256 KB
s1_12.txt AC 1 ms 256 KB
s1_13.txt AC 1 ms 2304 KB
s2_14.txt AC 8 ms 2816 KB
s2_15.txt AC 9 ms 896 KB
s2_16.txt AC 129 ms 8832 KB
s2_17.txt AC 105 ms 7424 KB
s2_18.txt AC 191 ms 12800 KB
s2_19.txt AC 198 ms 12800 KB
s2_20.txt AC 194 ms 12800 KB
s2_21.txt AC 191 ms 12800 KB
s2_22.txt AC 8 ms 768 KB
s2_23.txt AC 9 ms 896 KB
s2_24.txt AC 9 ms 2816 KB
s2_25.txt AC 235 ms 12800 KB
s2_26.txt AC 235 ms 12800 KB
s2_27.txt AC 235 ms 12800 KB
s2_28.txt AC 235 ms 12800 KB
s3_29.txt AC 191 ms 7808 KB
s3_30.txt AC 278 ms 6144 KB
s3_31.txt AC 161 ms 10240 KB
s3_32.txt AC 475 ms 11520 KB
s3_33.txt AC 194 ms 7040 KB
s3_34.txt AC 549 ms 14208 KB
s3_35.txt AC 545 ms 14208 KB
s3_36.txt AC 547 ms 14208 KB
s3_37.txt AC 544 ms 14208 KB
s3_38.txt AC 544 ms 14208 KB
s3_39.txt AC 547 ms 14208 KB
s3_40.txt AC 240 ms 1024 KB
s3_41.txt AC 247 ms 3072 KB