| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 172437 |
2020-01-01T14:33:10 Z |
mhy908 |
Candies (JOI18_candies) |
C++14 |
|
5 ms |
632 KB |
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
set<pair<LL, int> > pq;
set<pii> s;
int n;
LL arr[200010], sum[2][200010];
void relax(int num){
auto it=s.lower_bound(mp(num, inf));
set<pii>::iterator ithi, itlo;
bool hifl=false, lofl=false;
if(it==s.end())hifl=true;
else ithi=it;
it--;
if(it==s.begin())lofl=true;
else{
it--;
itlo=it;
it++;
}
int st, fin;
if(lofl)st=it->F;
else{
LL tsum=sum[itlo->S%2][itlo->S]-sum[itlo->S%2][itlo->F-1];
if(pq.find(mp(tsum, itlo->F))!=pq.end())pq.erase(mp(tsum, itlo->F));
else pq.erase(mp(-tsum, itlo->F));
st=itlo->F;
}
if(hifl)fin=it->S;
else{
LL tsum=sum[ithi->S%2][ithi->S]-sum[ithi->S%2][ithi->F-1];
if(pq.find(mp(tsum, ithi->F))!=pq.end())pq.erase(mp(tsum, ithi->F));
else pq.erase(mp(-tsum, ithi->F));
fin=ithi->S;
}
LL ttsum=sum[it->S%2][it->S]-sum[it->S%2][it->F-1];
if(pq.find(mp(ttsum, it->F))!=pq.end())pq.erase(mp(ttsum, it->F));
else pq.erase(mp(-ttsum, it->F));
s.erase(it);
if(!lofl)s.erase(itlo);
if(!hifl)s.erase(ithi);
ttsum=sum[1-fin%2][fin]-sum[1-fin%2][st-1];
if((fin-num)%2&&fin!=n)pq.insert(mp(-ttsum, st));
else pq.insert(mp(ttsum, st));
s.insert(mp(st, fin));
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++){
s.insert(mp(i, i));
scanf("%lld", &arr[i]);
pq.insert(mp(arr[i], i));
sum[i%2][i]=sum[i%2][i-1]+arr[i];
sum[1-i%2][i]=sum[1-i%2][i-1]-arr[i];
}
LL ans=0;
for(int i=1; i<=(n+1)/2; i++){
auto it=pq.end();
it--;
pii t=*it;
ans+=t.F;
printf("%lld\n", ans);
relax(t.S);
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
candies.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &arr[i]);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
