Submission #226827

#	Time	Username	Problem	Language	Result	Execution time	Memory
226827		Evirir	Solar Storm (NOI20_solarstorm)	C++17	18 / 100	2098 ms	154028 KiB

SolarStorm

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 1000005
#define LG 22

int DEBUG=0;

ll n,s,K;
ll d[MAXN],v[MAXN];
ll loc[MAXN];
viii seg;
int prt[MAXN][LG];

int goup(int u, int h){
	for(int i=LG-1;i>=0;i--){
		if(DEBUG) cout<<"test: u="<<u<<" i="<<i<<" prt[u][i]="<<prt[u][i]<<'\n';
		if(h&(1LL<<i) && prt[u][i]!=-1){
			if(DEBUG) cout<<"u="<<'\n';
			u=prt[u][i];
		}
	}
	return u;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	mset(prt,-1);
	
	cin>>n>>s>>K;
	for(int i=1;i<n;i++){
		cin>>d[i];
		if(i>0) loc[i]=loc[i-1]+d[i];
	}
	for(int i=0;i<n;i++){
		cin>>v[i];
		if(i>0) v[i]+=v[i-1];
	}
	
	for(int i=0;i<n;i++){
		ll L=lower_bound(loc, loc+n, loc[i]-K)-loc;
		ll R=upper_bound(loc, loc+n, loc[i]+K)-loc-1;
		seg.pb({{L,R},i});
	}
	
	for(int i=0;i<seg.size();i++){
		while(i<seg.size()-1 && seg[i].F.F==seg[i+1].F.F) seg.erase(seg.begin()+i);
	}
	
	if(DEBUG){
		for(int i=0;i<seg.size();i++) cout<<"i="<<i<<" ["<<seg[i].F.F<<","<<seg[i].F.S<<"] ("<<seg[i].S<<")"<<'\n';
	}
	
	for(int i=0;i<seg.size();i++){
		prt[i][0]=(--upper_bound(seg.begin(),seg.end(),iii(ii(seg[i].F.S+1,INF),INF)))->S;
		if(DEBUG) cout<<"i="<<i<<" ["<<seg[i].F.F<<","<<seg[i].F.S<<"] prt="<<prt[i][0]<<'\n';
	}
	for(int j=1;j<LG;j++){
		for(int i=0;i<seg.size();i++){
			if(prt[i][j-1]!=-1) prt[i][j]=prt[prt[i][j-1]][j-1];
		}
	}
	
	ll ans=-1, ansidx=0;
	for(int i=0;i<seg.size();i++){
		int p=goup(i,s-1);
		iii L=seg[i];
		iii R=seg[p];
		
		if(DEBUG) cout<<"i="<<i<<" p="<<p<<'\n';
		ll cur=v[R.F.S]-(L.F.F==0 ? 0LL : v[L.F.F-1]);
		if(DEBUG) cout<<"i="<<i<<" cur="<<cur<<" l="<<L.F.F<<" r="<<R.F.S<<'\n';
		if(cur>ans){
			ans=cur;
			ansidx=i;
		}
	}
	
	vi v;
	int cur=ansidx;
	for(int i=0;i<s;i++){
		if(DEBUG) cout<<"cur="<<cur<<" prt[cur]="<<prt[cur][0]<<'\n';
		if(cur==-1) break;
		v.pb(seg[cur].S);
		if(seg[cur].S==n-1) break;
		if(cur==prt[cur][0]) break;
		cur=prt[cur][0];
	}
	
	cout<<v.size()<<'\n';
	for(int i=0;i<v.size();i++){
		cout<<v[i]+1<<" ";
	}
	cout<<'\n';
	
	if(DEBUG) cout<<"Sum="<<ans<<'\n';
	
	return 0;
}

Compilation message (stderr)

SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<seg.size();i++){
              ~^~~~~~~~~~~
SolarStorm.cpp:73:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i<seg.size()-1 && seg[i].F.F==seg[i+1].F.F) seg.erase(seg.begin()+i);
         ~^~~~~~~~~~~~~
SolarStorm.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<seg.size();i++) cout<<"i="<<i<<" ["<<seg[i].F.F<<","<<seg[i].F.S<<"] ("<<seg[i].S<<")"<<'\n';
               ~^~~~~~~~~~~
SolarStorm.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<seg.size();i++){
              ~^~~~~~~~~~~
SolarStorm.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<seg.size();i++){
               ~^~~~~~~~~~~
SolarStorm.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<seg.size();i++){
              ~^~~~~~~~~~~
SolarStorm.cpp:117:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
              ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 8 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30