| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 30532 |
2017-07-24T13:08:58 Z |
inqr |
Holiday (IOI14_holiday) |
C++14 |
|
5000 ms |
10548 KB |
#include "holiday.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define ll long long
#define pii pair < int , int >
#define DB printf("debug\n");
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define all(x) x.begin() , x.end()
using namespace std;
int citynum,citystart,timee,att;
struct node{
int sbtrsum,sbtrnc,act;
node(){
sbtrsum=0,sbtrnc=0,act=0;
}
}nd;
node st[400005];
int citynotostp[400005];
int cityatt[100005];
int lastl=1,lastr=0;
void update(int cityno,node n,int ul,int ur,int l,int r,int stp){
if(l>r||ur<l||r<ul)return;
//printf("ul=%d ur=%d l=%d r=%d\n",ul,ur,l,r);
if(ul<=l&&r<=ur){
citynotostp[cityno]=l;
st[stp]=n;
return;
}
int m=(l+r)/2;
update(cityno,n,ul,ur,l,m,stp*2+1);update(cityno,n,ul,ur,m+1,r,stp*2+2);
st[stp].sbtrnc=st[stp].sbtrsum=st[stp].act=0;
if(st[stp*2+1].act==1){
//printf("za1\n");
st[stp].act=1;
st[stp].sbtrsum+=st[stp*2+1].sbtrsum;
st[stp].sbtrnc+=st[stp*2+1].sbtrnc;
}
if(st[stp*2+2].act==1){
//printf("za2\n");
st[stp].act=1;
st[stp].sbtrsum+=st[stp*2+2].sbtrsum;
st[stp].sbtrnc+=st[stp*2+2].sbtrnc;
}
//printf("u2:l=%d r=%d sbtrsum=%d sbtrnc=%d act=%d\n",l,r,st[stp].sbtrsum,st[stp].sbtrnc,st[stp].act);
}
ll sumofbestn(int n,int l,int r,int stp){
if(l>r || n<1 || st[stp].act==0)return 0;
if(st[stp].sbtrnc==n)return st[stp].sbtrsum;
int m=(l+r)/2;
ll ret=0;
ret+=sumofbestn(st[stp*2+1].sbtrnc,l,m,stp*2+1);
n-=st[stp].sbtrnc;
ret+=sumofbestn(n,m+1,r,stp*2+2);
return ret;
}
void autoupd(int nl,int nr){
node nodee;
nodee.act=1;
nodee.sbtrnc=1;
while(lastr<nr){
lastr++;
nodee.sbtrsum=cityatt[lastr];
update(lastr,nodee,citynotostp[lastr],citynotostp[lastr],0,citynum-1,0);
}
while(nl<lastl){
lastl--;
nodee.sbtrsum=cityatt[lastl];
update(lastl,nodee,citynotostp[lastl],citynotostp[lastl],0,citynum-1,0);
}
nodee.act=0;
while(lastr>nr){
nodee.sbtrsum=cityatt[lastr];
update(lastr,nodee,citynotostp[lastr],citynotostp[lastr],0,citynum-1,0);
lastr--;
}
while(lastl<nl){
nodee.sbtrsum=cityatt[lastl];
update(lastl,nodee,citynotostp[lastl],citynotostp[lastl],0,citynum-1,0);
lastl++;
}
}
ll solve(){
ll ans=0;
for(int i=0;i<=timee;i++){
int cityleft=citystart-i;
if(cityleft<0)continue;
for(int j=0;min(j,i)*2+max(i,j)<=timee;j++){
int cityright=citystart+j;
if(cityright>=citynum)continue;
//printf(" cityright=%d\n",cityright);
autoupd(cityleft,cityright);
int visitable=timee-min(j,i)*2-max(i,j);
//printf(" visitable=%d\n",visitable);
ans=max(ans,sumofbestn(visitable,0,citynum-1,0));
//printf(" ans=%lld\n",ans);
}
}
return ans;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
citynum=n,citystart=start,timee=d;
vector < pii > attind;
for(int i=0;i<n;i++){
attind.pb(mp(attraction[i],i));
cityatt[i]=attraction[i];
}
sort(all(attind));reverse(all(attind));
for(int i=0;i<n;i++){
node nodeee;
nodeee.sbtrnc=1;
nodeee.sbtrsum=attind[i].st;
nodeee.act=0;
//printf("%d %d\n",attind[i].st,attind[i].nd);
update(attind[i].nd,nodeee,i,i,0,n-1,0);
}
return solve();
}
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
10548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
9076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5000 ms |
10548 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
