Submission #302598

#	Time	Username	Problem	Language	Result	Execution time	Memory
302598		Dremix10	Comparing Plants (IOI20_plants)	C++17	0 / 100	1 ms	256 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end();
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<","<<#y<<" = "<<"("<<x<<"-"<<y<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;

vector<int> arr,bigger;


vector<int> seg;
vector<int> laz;
vector<int> pou;

void join(int par, int x, int y){
    if(seg[x]<seg[y]){
        seg[par] = seg[x];
        pou[par] = pou[x];
    }
    else{
        seg[par] = seg[y];
        pou[par] = pou[y];
    }
}

void push(int par, int x, int y){
    seg[x] += laz[par];
    laz[x] += laz[par];
    seg[y] += laz[par];
    laz[y] += laz[par];
    laz[par] = 0;
}

void build(int s, int e, int idx){
    if(s==e){
        seg[s] = 1e9;
        pou[s] = s;
        return;
    }
    int mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    join(idx,idx*2,idx*2+1);
}

void update(int s, int e, int idx, int qs, int qe, int x){
    if(qs<=s && e<=qe){
        seg[idx] += x;
        laz[idx] += x;
        return;
    }
    if(s>qe || e<qs)return;
    int mid = (s+e)/2;
    push(idx,idx*2,idx*2+1);
    update(s,mid,idx*2,qs,qe,x);
    update(mid+1,e,idx*2+1,qs,qe,x);
    join(idx,idx*2,idx*2+1);
}


void init(int k, vector<int> r) {
	int n = r.size();
	arr.assign(n,0);
    bigger.assign(n,0);
    seg.assign((n+5)*4,0);
    laz.assign((n+5)*4,0);
    pou.assign((n+5)*4,0);
    int i,j;
    build(0,n-1,1);

    for(i=0;i<n;i++){
        if(r[i]==0){
            if(i+1<n){
                update(0,n-1,1,i+1,min(n-1,i+k-1),1);
            }
            if(i+k-1>=n){
                update(0,n-1,1,0,(i+k-1)%n,1);
            }
            update(0,n-1,1,i,i,-1e9);
        }
    }

    int curr = n;

    for(int t=0;t<n;t++){

        int x = pou[0];
        arr[x] = curr--;
        update(0,n-1,1,x,x,1e9);
        //pv(arr)
        //for(auto xx : s)
        //    cout<<xx.pos<<" ";
        //cout<<endl;
        //pv(bigger)
        //pv(r)
        //cout<<endl;
        if(x+1<n){
                update(0,n-1,1,x+1,min(n-1,x+k-1),-1);
            }
            if(x+k-1>=n){
                update(0,n-1,1,0,(x+k-1)%n,-1);
            }
        for(j=1;j<k;j++){
            //cout<<j<<" "<<k<<endl;



            int idx = x-j;
            if(idx<0)idx+=n;
            if(r[idx]>0){
                r[idx]--;
                if(r[idx]==0){
                    if(idx+1<n){
                        update(0,n-1,1,idx+1,min(n-1,idx+k-1),1);
                    }
                    if(idx+k-1>=n){
                        update(0,n-1,1,0,(idx+k-1)%n,1);
                    }
                    update(0,n-1,1,idx,idx,-1e9);
                }
            }
        }

        //pv(bigger)
        //pv(zer)
        //pv(r)

	}
    pv(arr)

}


int compare_plants(int x, int y) {
    if(arr[x]>arr[y])return 1;
    return -1;

}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25