제출 #397304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397304		Antekb	식물 비교 (IOI20_plants)	C++14	44 / 100	1644 ms	16808 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define st first
#define nd second
using namespace std;
const int N=(1<<18);
int lazy[2*N], maks[2*N];
void prop1(int v){
    if(!lazy[v] || v>N)return;
    int l=2*v, r=l+1;
    lazy[l]+=lazy[v];
    lazy[r]+=lazy[v];
    maks[l]+=lazy[v];
    maks[r]+=lazy[v];
    lazy[v]=0;
}
void add(int v, int l, int r ,int L, int R, int c){
    //if(v==1)cout<<"a"<<l<<" "<<r<<" "<<c<<"\n";
    //cout<<v<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
    if(l==L && r==R){
        lazy[v]+=c;
        maks[v]+=c;
        return;
    }
    prop1(v);
    int M=(L+R)>>1;
    if(l<=M)add(2*v, l, min(M, r), L, M, c);
    if(r>M)add(2*v+1, max(M+1, l), r, M+1, R, c);
    maks[v]=max(maks[2*v], maks[2*v+1]);
    return;
}
int lazy2[2*N];
pair<int, int> ma[2*N];
void prop2(int v){
    if(!lazy2[v] || v>N)return;
    int l=2*v, r=l+1;
    lazy2[l]+=lazy2[v];
    lazy2[r]+=lazy2[v];
    ma[l].st+=lazy2[v];
    ma[r].st+=lazy2[v];
    lazy2[v]=0;
}
void add2(int v, int l, int r ,int L, int R, int c){
    //if(v==1)cout<<"b"<<l<<" "<<r<<" "<<c<<"\n";
    //cout<<"c"<<"\n";
    if(l==L && r==R){
        lazy2[v]+=c;
        ma[v].st+=c;
        return;
    }
    prop2(v);
    int M=(L+R)>>1;
    if(l<=M)add2(2*v, l, min(M, r), L, M, c);
    if(r>M)add2(2*v+1, max(M+1, l), r, M+1, R, c);
    ma[v]=max(ma[2*v], ma[2*v+1]);
    return;
}
void check(int k, int n){
    while(maks[1]==k){
        //cout<<"b\n";
        int v=1;
        while(v<N){
            prop1(v);
            if(maks[2*v]==k)v*=2;
            else v=2*v+1;
        }
        add(1, v-N, v-N, 0, N-1, -N);
        add2(1, v-N, v-N, 0, N-1, N);
        if(v-N<n-1)add2(1, v-N+1, min(v-N+k, n-1), 0, N-1, -1);
        if(v-N+k>=n)add2(1, 0, v-N+k-n, 0, N-1, -1);
    }
}
vector<int> V, V2;
void init(int k, std::vector<int> r) {
    int n=r.size();
    k--;
    V.resize(n);
    for(int i=0; i<n; i++){
        ma[N+i].nd=i;
        maks[N+i]=r[i];
    }
    for(int i=N-1; i>0; i--){
        ma[i]=max(ma[2*i], ma[2*i+1]);
        maks[i]=max(maks[2*i], maks[2*i+1]);
    }
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
    	int j=ma[1].nd;
        //cout<<j<<"\n";
    	V[j]=i;
    	add2(1, j, j, 0, N-1, -N);
        if(j<n-1)add2(1, j+1, min(j+k, n-1), 0, N-1, 1);
        if(j+k>=n)add2(1, 0, j+k-n, 0, N-1, 1);
    	if(j)add(1, max(j-k, 0), j-1, 0, N-1, 1);
        if(j-k<0)add(1, n+j-k, n-1, 0, N-1, 1);
    }
    V2.resize(n);
    for(int i=0; i<2*N; i++){
        ma[i]=make_pair(0, 0);
        maks[i]=0;
        lazy[i]=0;
        lazy2[i]=0;
    }
    for(int i=0; i<n; i++){
        ma[N+i].nd=-i;
        maks[N+i]=r[i];
    }
    for(int i=N-1; i>0; i--){
        ma[i]=max(ma[2*i], ma[2*i+1]);
        maks[i]=max(maks[2*i], maks[2*i+1]);
    }
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
        int j=-ma[1].nd;
        //cout<<j<<"\n";
        V2[j]=i;
        add2(1, j, j, 0, N-1, -N);
        if(j<n-1)add2(1, j+1, min(j+k, n-1), 0, N-1, 1);
        if(j+k>=n)add2(1, 0, j+k-n, 0, N-1, 1);
        if(j)add(1, max(j-k, 0), j-1, 0, N-1, 1);
        if(j-k<0)add(1, n+j-k, n-1, 0, N-1, 1);
    }
	return;
}     
int compare_plants(int x, int y){
	if(V[x]<V[y] && V2[x]<V2[y])return -1;
	if(V[x]>V[y] && V2[x]>V2[y])return 1;
   	return 0;
}

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