Submission #3313588
Source Code Expand
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <string> #include <sstream> #include <complex> #include <vector> #include <list> #include <queue> #include <deque> #include <stack> #include <map> #include <set> using namespace std; #define mod 1000000007 #define FOR(x,to) for(int x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define long long long inline int rei(){int x;cin>>x;return x;} inline long rel(){long x;cin>>x;return x;} inline string res(){string x;cin>>x;return x;} //------------------------------------------------------- long A[200000]; long B[200000]; void Calc(){ int N = rei()*2; int Q = rei(); for(int i=0;i<N;i++){ A[i] = rel(); } for(int i=0;i<N;i++){ B[i] = rel(); } priority_queue<long,vector<long>,greater<long>> Abigger; priority_queue<long,vector<long>,greater<long>> Abiggerdelete; priority_queue<long,vector<long>,greater<long>> Bbigger; priority_queue<long,vector<long>,greater<long>> Bbiggerdelete; int Anum = 0; int Bnum = 0; long sum = A[0] + A[N-1]; for(int i=1;i<N-1;i++){ if(A[i] >= B[i]){ Abigger.push(A[i]-B[i]); Anum++; sum += A[i]; } else{ Bbigger.push(B[i]-A[i]); Bnum++; sum += B[i]; } } for(int query=0;query<Q;query++){ int p = rei()-1; if(p == 0 || p == N-1){ sum -= A[p]; } else{ if(A[p] >= B[p]){ sum -= A[p]; Abiggerdelete.push(A[p]-B[p]); Anum--; } else{ sum -= B[p]; Bbiggerdelete.push(B[p]-A[p]); Bnum--; } } A[p] = rel(); B[p] = rel(); if(p == 0 || p == N-1){ sum += A[p]; } else{ if(A[p] >= B[p]){ Abigger.push(A[p]-B[p]); Anum++; sum += A[p]; } else{ Bbigger.push(B[p]-A[p]); Bnum++; sum += B[p]; } } long ans = sum; if(Anum % 2){ while(!Abiggerdelete.empty() && Abigger.top() == Abiggerdelete.top()){ Abigger.pop(); Abiggerdelete.pop(); } while(!Bbiggerdelete.empty() && Bbigger.top() == Bbiggerdelete.top()){ Bbigger.pop(); Bbiggerdelete.pop(); } ans -= min(Abigger.top(),Bbigger.top()); } cout << ans << endl; } } int main(int argc,char** argv){ ios::sync_with_stdio(false), cin.tie(0); cout.tie(0); Calc(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Paired Parentheses |
User | leign |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2460 Byte |
Status | AC |
Exec Time | 247 ms |
Memory | 8932 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 300 / 300 | 200 / 200 | ||||||||
Status |
|
|
|
|
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 | 3 ms | 512 KB |
s2_15.txt | AC | 3 ms | 640 KB |
s2_16.txt | AC | 32 ms | 4152 KB |
s2_17.txt | AC | 26 ms | 3008 KB |
s2_18.txt | AC | 45 ms | 5064 KB |
s2_19.txt | AC | 44 ms | 5228 KB |
s2_20.txt | AC | 44 ms | 5228 KB |
s2_21.txt | AC | 44 ms | 5084 KB |
s2_22.txt | AC | 3 ms | 512 KB |
s2_23.txt | AC | 3 ms | 640 KB |
s2_24.txt | AC | 3 ms | 512 KB |
s2_25.txt | AC | 47 ms | 5228 KB |
s2_26.txt | AC | 48 ms | 5228 KB |
s2_27.txt | AC | 48 ms | 5228 KB |
s2_28.txt | AC | 47 ms | 5228 KB |
s3_29.txt | AC | 77 ms | 3572 KB |
s3_30.txt | AC | 148 ms | 3912 KB |
s3_31.txt | AC | 43 ms | 4468 KB |
s3_32.txt | AC | 214 ms | 7124 KB |
s3_33.txt | AC | 77 ms | 3656 KB |
s3_34.txt | AC | 240 ms | 8932 KB |
s3_35.txt | AC | 238 ms | 8504 KB |
s3_36.txt | AC | 240 ms | 7404 KB |
s3_37.txt | AC | 237 ms | 7276 KB |
s3_38.txt | AC | 247 ms | 7276 KB |
s3_39.txt | AC | 238 ms | 7404 KB |
s3_40.txt | AC | 184 ms | 1024 KB |
s3_41.txt | AC | 189 ms | 1024 KB |