Submission #869190

#	Time	Username	Problem	Language	Result	Execution time	Memory
869190		PenguinsAreCute	Candies (JOI18_candies)	C++17	0 / 100	1 ms	596 KiB

candies

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
#pragma optimize("PLEASE_GIVE_ACCEPTED")
#define int long long
using ll = long long;
using ii = pair<int,int>;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define pu emplace
#define pf emplace_front
#define sz(v) (int)(v.size())
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a-1;i>=b;i--)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define dieded(k) do {cout<<k; return 0;} while(0)
// Ordered set
// https://codeforces.com/blog/entry/11080
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
// Modular Arithmetic
template<int MOD> struct mint {
	explicit operator ll() const {return v;}
	mint(ll _v) {v=int32_t(_v%MOD); if(v<0) v+=MOD;}
	mint() {v=0;}
	mint& operator += (mint y) {v+=y.v; if(v>=MOD) v-=MOD; return *this;}
	mint& operator -= (mint y) {v-=y.v; if(v<0) v+=MOD; return *this;}
	mint& operator *= (mint y) {v=int32_t((1LL*v*y.v)%MOD); return *this;}
	friend mint operator + (mint x, mint y) {return x+=y;}
	friend mint operator - (mint x, mint y) {return x-=y;}
	friend mint operator * (mint x, mint y) {return x*=y;}
	friend mint pow (mint base, int expo) {
		expo %= (MOD-1);
		if(expo<0) expo+=(MOD-1);
		return internal_pow(base, expo);
	}
	private:
		int32_t v;
		friend mint internal_pow(mint base, int expo) {
			if(expo==0) return 1;
			return internal_pow(base * base, expo >> 1) * (expo & 1 ? base : 1);
		}
};
using mt1 = mint<998244353>;
using mt2 = mint<1000000007>;
#ifdef DEBUG
	#define debug if(1)
	#define RTEfind cout<<"RTE check (line "<<__LINE__<<")\n"
	#define state(...) do {cout<<"Line "<<__LINE__<<": "; printf(__VA_ARGS__);} while(0)
#else
	#define debug if(0)
	#define RTEfind 42
	#define state(...) 69
#endif
inline int readInt() {
    int x; cin >> x;
    return x;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// segtree
// https://codeforces.com/blog/entry/18051
ii seg[401210];
int n;
void build() {
	RREP(i,n,1) seg[i]=max(seg[i<<1],seg[i<<1|1]);
}
void up(int x, int v) {
	for(seg[x+=n].fi=v;x>1;x>>=1) seg[x>>1]=max(seg[x],seg[x^1]);
}
ii qry(int l, int r) {
	ii ans = mp(-6912102010,0);
	for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
		if(l&1) ans=max(ans,seg[l++]);
		if(r&1) ans=max(ans,seg[--r]);
	}
	return ans;
}
void eat(int x, int cst, int prv[], int nxt[]) {
	int new_candy = -(6912102010LL << 1)-cst;
	if(prv[x]!=-1) {
		new_candy += 6912102010+qry(prv[x],prv[x]+1).fi;
		up(prv[x],-6912102010);
		state("update %lld to -INF\n",prv[x]);
		prv[x]=prv[prv[x]];
	}
	if(nxt[x]!=-1) {
		new_candy += 6912102010+qry(nxt[x],nxt[x]+1).fi;
		up(nxt[x],-6912102010);
		state("update %lld to -INF\n",nxt[x]);
		nxt[x]=nxt[nxt[x]];
	}
	if(prv[x]!=-1) nxt[prv[x]]=(new_candy<-2010121069?nxt[x]:x);
	if(nxt[x]!=-1) prv[nxt[x]]=(new_candy<-2010121069?prv[x]:x);
	state("update %lld to %lld\n",x,new_candy);
	up(x,new_candy);
}
int32_t main() {
	#ifdef DEBUG
		auto programstarttime=high_resolution_clock::now();
	#else
		ios_base::sync_with_stdio(0);
		cin.tie(0);
	#endif
	n = readInt();
	state("n=%lld\n",n);
	int prv[n], nxt[n], a[n], cur=0;
	REP(i,0,n) {
		a[i]=readInt();
		seg[i+n]=mp(a[i],i);
		prv[i]=i-1;
		nxt[i]=(i==n-1?-1:i+1);
	}
	state("hi\n");
	build();
	while(1) {
		ii best = qry(0,n);
		state("best=(%lld,%lld)\n",best.fi,best.se);
		if(best.fi<-2010121069) break;
		cur+=best.fi;
		cout<<cur<<"\n";
		eat(best.se,best.fi,prv,nxt);
	}
	#ifdef DEBUG
		auto programendtime=high_resolution_clock::now();
		duration<long double, milli> programdur=programendtime-programstarttime;
		cout<<"\nProgram took "<<programdur.count()<<" milliseconds";
	#endif
}

Compilation message (stderr)

candies.cpp:6: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    6 | #pragma optimize("PLEASE_GIVE_ACCEPTED")
      | 
candies.cpp: In function 'void eat(long long int, long long int, long long int*, long long int*)':
candies.cpp:65:21: warning: statement has no effect [-Wunused-value]
   65 |  #define state(...) 69
      |                     ^~
candies.cpp:95:3: note: in expansion of macro 'state'
   95 |   state("update %lld to -INF\n",prv[x]);
      |   ^~~~~
candies.cpp:65:21: warning: statement has no effect [-Wunused-value]
   65 |  #define state(...) 69
      |                     ^~
candies.cpp:101:3: note: in expansion of macro 'state'
  101 |   state("update %lld to -INF\n",nxt[x]);
      |   ^~~~~
candies.cpp:65:21: warning: statement has no effect [-Wunused-value]
   65 |  #define state(...) 69
      |                     ^~
candies.cpp:106:2: note: in expansion of macro 'state'
  106 |  state("update %lld to %lld\n",x,new_candy);
      |  ^~~~~
candies.cpp: In function 'int32_t main()':
candies.cpp:65:21: warning: statement has no effect [-Wunused-value]
   65 |  #define state(...) 69
      |                     ^~
candies.cpp:117:2: note: in expansion of macro 'state'
  117 |  state("n=%lld\n",n);
      |  ^~~~~
candies.cpp:65:21: warning: statement has no effect [-Wunused-value]
   65 |  #define state(...) 69
      |                     ^~
candies.cpp:125:2: note: in expansion of macro 'state'
  125 |  state("hi\n");
      |  ^~~~~
candies.cpp:65:21: warning: statement has no effect [-Wunused-value]
   65 |  #define state(...) 69
      |                     ^~
candies.cpp:129:3: note: in expansion of macro 'state'
  129 |   state("best=(%lld,%lld)\n",best.fi,best.se);
      |   ^~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92