이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define Nmax 500001
long N,Q,A[Nmax],S[Nmax] ={};
bool ss(tuple<long,long,long> a,tuple<long,long,long> b){
return get<0>(a) < get<0>(b);
}
bool operator<(pair<long,long> a , pair<long,long> b){
if(a.first == b.first) return a.second<b.second;
return a.first<b.first;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
set<pair<long,long>> then;
set<pair<long,long>> now;
set<pair<long,long>> past;
long then_val = -1;
long now_val = 0;
now.insert(make_pair(0,0));
cin>>N;
for (long i = 1;i<=N;i++){
cin>>A[i];
S[i] = S[i-1]+A[i];
//first element to be greater than value;
long bound = S[i];
auto pointer = now.upper_bound(make_pair(S[i],1000000001));
if(pointer==now.begin()){
auto new_pointer = then.upper_bound(make_pair(S[i],1000000001));
new_pointer--;
long delta = S[i]-new_pointer->second;
now.insert(make_pair(S[i]+delta,S[i]));
} else{
then_val++;
now_val++;
pointer--;
long delta = S[i]-pointer->second;
//swap(past,now);
swap(then,now);
now.clear();
//cout<<S[i]+delta<<" "<<S[i]<<" "<<pointer->second<<" "<<endl;
now.insert(make_pair(S[i]+delta,S[i]));
}
}
cout<<now_val;
}
/*
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
long l[Nmax];
long r[Nmax];
long fi[Nmax] ={};
long specialloc[Nmax] ={};
long startspecial[3][Nmax] = {};
long endspecial[3][Nmax] = {};
long comlen = 1;
cin>>N>>Q;
cin>>s;
string com;
com += s[0];
fi[1] = 0;
for(long i = 1;i<=N-1;i++){
if(s[i]!=s[i-1]) {comlen++; com += s[i];}
fi[i+1] = comlen - 1;
}
for(long i = 1;i<=Q;i++){
cin>>l[i]>>r[i];
l[i] = fi[l[i]];
r[i] = fi[r[i]];
long ans = 0;
long delta = r[i]- l[i]+1;
if(com[l[i]]==com[r[i]]) delta--;
while(delta>=4){
delta -=2;
ans++;
}
ans += delta - 1;
cout<<max(ans,(long)0)<<endl;
}
}
//com += '0';
/*vector<tuple<long,long,long>> special;
for(char i = 'A';i<='C';i++){
long lastfound = -1;
for (long j = 0;j<=comlen;j++){
if (j==comlen) com[j]=i;
if(com[j]==i){
if((j-lastfound)>3){
//cout<<j<<" "<<lastfound<<endl;
special.push_back(make_tuple((long)lastfound+1,(long)j-1,(long)(i-'A')));
specialloc[lastfound+1]++;
specialloc[j-1]--;
}
lastfound = j;
}
}
}
sort(special.begin(),special.end(),ss);
for (auto i: special){
long a,b,c;
tie(a,b,c) = i;
long need_to_end_at_or_after = a + 2;
long need_to_start_at_or_before = b - 2;
if(specialloc[a]==0){
endspecial[(long)(i-'A')][a-1];
} else{
}
if(specialloc[b]==0){
} else{
}
}
//cout<<com<<endl;
*/
컴파일 시 표준 에러 (stderr) 메시지
segments.cpp:99:5: warning: "/*" within comment [-Wcomment]
99 | /*vector<tuple<long,long,long>> special;
|
segments.cpp: In function 'int main()':
segments.cpp:33:14: warning: unused variable 'bound' [-Wunused-variable]
33 | long bound = S[i];
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |