oj.uz

Submission #391208

# Submission time Handle Problem Language Result Execution time Memory
391208 2021-04-18T08:39:37 Z nathanlee726 Candies (JOI18_candies) C++14
100 / 100
 143 ms 12524 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int a[200010],pre[200010],nxt[200010],o[200010];
priority_queue<pii,vector<pii>,less<pii> >pq;
signed main(){
	IOS();
	int n;
	cin>>n;
	F(n)cin>>a[i];
	a[n]=-1e18;
	F(n+1)pre[i]=i-1,nxt[i]=i+1;
	pre[0]=n,nxt[n]=0;
	F(n+1)pq.push({a[i],i});
	int ind=0,ans=0;
	while(1){
		pii pi=pq.top();
		pq.pop();
		if(pre[nxt[pi.Y]]!=pi.Y)continue;
		ans+=pi.X,ind++;
		o[ind]=max(o[ind],ans);
		bug(ind,ans,pre[pi.Y],nxt[pi.Y]);
		if((pre[pi.Y]==nxt[pi.Y])||((pre[pi.Y]+1)%(n+1)==nxt[pi.Y]))break;
		pi.X=(a[pre[pi.Y]]+a[nxt[pi.Y]]-pi.X);
		a[pi.Y]=pi.X;
		pre[pi.Y]=pre[pre[pi.Y]],nxt[pre[pi.Y]]=pi.Y;
		nxt[pi.Y]=nxt[nxt[pi.Y]],pre[nxt[pi.Y]]=pi.Y;
		pq.push(pi);
	} 
	F(ceiling(n,2))cout<<o[i+1]<<endl;
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 460 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 123 ms 12484 KB Output is correct
22 Correct 123 ms 12392 KB Output is correct
23 Correct 123 ms 12428 KB Output is correct
24 Correct 92 ms 12272 KB Output is correct
25 Correct 94 ms 12360 KB Output is correct
26 Correct 90 ms 12320 KB Output is correct
27 Correct 99 ms 12524 KB Output is correct
28 Correct 97 ms 12416 KB Output is correct
29 Correct 93 ms 12412 KB Output is correct
30 Correct 96 ms 12396 KB Output is correct
31 Correct 99 ms 12472 KB Output is correct
32 Correct 97 ms 12476 KB Output is correct
33 Correct 103 ms 12232 KB Output is correct
34 Correct 104 ms 12224 KB Output is correct
35 Correct 107 ms 12300 KB Output is correct
36 Correct 143 ms 12372 KB Output is correct
37 Correct 132 ms 12464 KB Output is correct
38 Correct 138 ms 12448 KB Output is correct
39 Correct 89 ms 12240 KB Output is correct
40 Correct 87 ms 12216 KB Output is correct
41 Correct 106 ms 12336 KB Output is correct
42 Correct 95 ms 12508 KB Output is correct
43 Correct 95 ms 12476 KB Output is correct
44 Correct 107 ms 12464 KB Output is correct
45 Correct 102 ms 12420 KB Output is correct
46 Correct 96 ms 12412 KB Output is correct
47 Correct 96 ms 12464 KB Output is correct
48 Correct 108 ms 12184 KB Output is correct
49 Correct 126 ms 12336 KB Output is correct
50 Correct 105 ms 12196 KB Output is correct