Submission #1131735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131735		8pete8	Tortoise (CEOI21_tortoise)	C++20	100 / 100	339 ms	66716 KiB

tortoise

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=5e5,inf=1e18,minf=-1e18,lg=30,base=191,Mx=1e5;
//#undef int
int n;
int have[mxn+10],dist[mxn+10],L[mxn+10],R[mxn+10];
int mark[mxn+10],arrival[mxn+10];
//ct=latest time arrving at i
struct seg{
    //keeping the min(2*(i-1)-cti)
	int v[4*mxn+10],add[4*mxn+10];
	void init(int n){for(int i=0;i<=4*(n+1);i++)v[i]=inf,add[i]=0;}
	void push(int l,int r,int pos){
        v[pos]+=add[pos];
		if(l!=r){
			add[pos*2]+=add[pos];
			add[pos*2+1]+=add[pos];
		}
        add[pos]=0;
	}
	void update(int l,int r,int ql,int qr,int pos,int val){
		if(qr<ql)return;
		push(l,r,pos);
		if(l>qr||r<ql)return;
		if(ql<=l&&r<=qr){
			add[pos]=val;
			push(l,r,pos);
			return;
		}
		int mid=l+(r-l)/2;
		update(l,mid,ql,qr,pos*2,val);
		update(mid+1,r,ql,qr,pos*2+1,val);
		v[pos]=min(v[pos*2],v[pos*2+1]);
	}
	int qryr(int l,int r,int ql,int qr,int pos){
		if(qr<ql)return inf;
		push(l,r,pos);
		if(l>qr||r<ql)return inf;
		if(ql<=l&&r<=qr)return v[pos];
		int mid=l+(r-l)/2;
		return min(qryr(l,mid,ql,qr,pos*2),qryr(mid+1,r,ql,qr,pos*2+1));
	}
	int qry(int l,int r,int pos,int qpos){
		push(l,r,pos);
		if(l==r)return v[pos];
		int mid=l+(r-l)/2;
		if(qpos<=mid)return qry(l,mid,pos*2,qpos);
		return qry(mid+1,r,pos*2+1,qpos);
	}
	void updatepos(int l,int r,int pos,int qpos,int val){
		push(l,r,pos);
        if(qpos<l||qpos>r)return;
		if(l==r){
            v[pos]=min(v[pos],val);
            return;
		}
		int mid=l+(r-l)/2;
        updatepos(l,mid,pos*2,qpos,val);
        updatepos(mid+1,r,pos*2+1,qpos,val);
		v[pos]=min(v[pos*2],v[pos*2+1]);
	}
	void updp(int pos,int val){updatepos(1,n,1,pos,val);}
	void updr(int l,int r,int val){update(1,n,l,r,1,val);}
	int q(int pos){return qry(1,n,1,pos);}
	int qr(int l,int r){return qryr(1,n,l,r,1);}
}t;
struct fen{
    int fwk[mxn+10];
    //keeping cti
    void update(int pos,int val){
        for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;
    }
    int qry(int pos){
        int sum=0;
        for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
        return sum;
    }
}ct;
int32_t main(){
    fastio
    cin>>n;
    int sum=0;
    int cl=0;
    for(int i=1;i<=n;i++){
        cin>>have[i];
        if(have[i]!=-1)sum+=have[i];
        else cl=i;
    }
    int last=inf;
    for(int i=1;i<=n;i++){
        L[i]=last;
        if(have[i]==-1)last=i;
    }
    last=inf;
    for(int i=n;i>=1;i--){
        R[i]=last;
        if(have[i]==-1)last=i;
    }
    vector<pii>v;
    for(int i=1;i<=n;i++)if(have[i]!=-1&&have[i]){
        if(abs(L[i]-i)<abs(R[i]-i)){
            arrival[i]=i-1;
            dist[i]=abs(L[i]-i);
        }
        else{
            arrival[i]=R[i]-1+R[i]-i;
            dist[i]=abs(R[i]-i);
        }
        ct.update(i,arrival[i]-ct.qry(i));
        v.pb({dist[i],i});
    }
    sort(all(v));
    //its optimal following this order?
    int ans=0;
    t.init(n);
    for(int i=v.size()-1;i>=0;i--){
        //take 1 free
        int cur=v[i].s;
        if(R[cur]==inf||mark[R[cur]])continue;
        t.updp(cur,cur-1);
        sum--;
        mark[R[cur]]=1;
        have[cur]--;
    }
    for(auto i:v){
        if(have[i.s]==0)continue;
        int k=ct.qry(i.s);
        int x=min(((2*(i.s-1))-k+(2*i.f))/(2*i.f),t.qr(i.s,n)/(2*i.f));
        x=min(have[i.s],x);
        x=max(0LL,x);
        ans+=x;
        ct.update(i.s,2*i.f*x);
        //if left we take first then take the free one
        if(abs(L[i.s]-i.s)<abs(R[i.s]-i.s))t.updr(i.s,n,-2*i.f*x);
        else t.updr(i.s+1,n,-2*i.f*x);
        t.updp(i.s,2*(i.s-1)-k-(2*(x-1)*i.f));
        //ct+2*(take-1)*dist<=2*(x-1)
        //take<=(2*(x-1-ct+(2*dist))/2(dist)
    }
    cout<<sum-ans<<'\n';
}
/*

-its optimal to use playgrounds and shops left to right
-if we move from playgrounds a->b we can buy 1 thing on the way 
if playgroud a is on the left of b then shops <=(a+b)/2 should go to playground a
the the other go to playground b
-its more optimal to prioritize the shop with the least dist from playground
if we have the dist then prioritize the first one (from the first claim)
*/

Compilation message (stderr)

tortoise.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
tortoise.cpp:44:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 |         void init(int n){for(int i=0;i<=4*(n+1);i++)v[i]=inf,add[i]=0;}
      |                        ^
tortoise.cpp:45:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 |         void push(int l,int r,int pos){
      |                                      ^
tortoise.cpp:53:62: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |         void update(int l,int r,int ql,int qr,int pos,int val){
      |                                                              ^
tortoise.cpp:67:51: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   67 |         int qryr(int l,int r,int ql,int qr,int pos){
      |                                                   ^
tortoise.cpp:75:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   75 |         int qry(int l,int r,int pos,int qpos){
      |                                             ^
tortoise.cpp:82:60: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   82 |         void updatepos(int l,int r,int pos,int qpos,int val){
      |                                                            ^
tortoise.cpp:94:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   94 |         void updp(int pos,int val){updatepos(1,n,1,pos,val);}
      |                                  ^
tortoise.cpp:95:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   95 |         void updr(int l,int r,int val){update(1,n,l,r,1,val);}
      |                                      ^
tortoise.cpp:96:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   96 |         int q(int pos){return qry(1,n,1,pos);}
      |                      ^
tortoise.cpp:97:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   97 |         int qr(int l,int r){return qryr(1,n,l,r,1);}
      |                           ^
tortoise.cpp:102:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  102 |     void update(int pos,int val){
      |                                ^
tortoise.cpp:105:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  105 |     int qry(int pos){
      |                    ^
tortoise.cpp:111:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  111 | int32_t main(){
      |              ^

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 25 / 25
• Subtask 5: 27 / 27