제출 #1178743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178743		guagua0407	식물 비교 (IOI20_plants)	C++20	44 / 100	1119 ms	26512 KiB

plants

#include "plants.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int inf=1e9;
    int n;
    struct segtree{
        vector<pair<int,int>> st;
        vector<int> lz;
        segtree(int _n){
            n=_n;
            st=vector<pair<int,int>>(n*4);
            lz=vector<int>(n*4);
        }
        void init(int l=0,int r=n-1,int v=1){
            if(l==r){
                st[v]={0,l};
                return;
            }
            int mid=(l+r)/2;
            init(l,mid,v*2);
            init(mid+1,r,v*2+1);
            st[v]=min(st[v*2],st[v*2+1]);
        }
        void push(int v){
            st[v*2].f+=lz[v];
            lz[v*2]+=lz[v];
            st[v*2+1].f+=lz[v];
            lz[v*2+1]+=lz[v];
            lz[v]=0;
        }
        void update(int tl,int tr,int val,int l=0,int r=n-1,int v=1){
            if(r<tl or tr<l){
                return;
            }
            if(tl<=l and r<=tr){
                st[v].f+=val;
                lz[v]+=val;
                return;
            }
            push(v);
            int mid=(l+r)/2;
            update(tl,min(mid,tr),val,l,mid,v*2);
            update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
            st[v]=min(st[v*2],st[v*2+1]);
        }
        pair<int,int> query(int tl,int tr,int l=0,int r=n-1,int v=1){
            if(r<tl or tr<l){
                return {inf,-1};
            }
            if(tl<=l and r<=tr){
                return st[v];
            }
            push(v);
            int mid=(l+r)/2;
            return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
        }
        void add(int l,int r,int val){
            if(r<0){
                l+=n;
                r+=n;
            }
            if(l>=n){
                l-=n;
                r-=n;
            }
            if(l<0){
                l+=n;
                update(l,n-1,val);
                update(0,r,val);
            }
            else if(r>=n){
                r-=n;
                update(l,n-1,val);
                update(0,r,val);
            }
            else{
                update(l,r,val);
            }
        }
    };
    struct segtree2{
        vector<pair<int,int>> st;
        vector<int> lz;
        segtree2(int _n){
            n=_n;
            st=vector<pair<int,int>>(n*4);
            lz=vector<int>(n*4);
        }
        void init(int l=0,int r=n-1,int v=1){
            if(l==r){
                st[v]={0,-l};
                return;
            }
            int mid=(l+r)/2;
            init(l,mid,v*2);
            init(mid+1,r,v*2+1);
            st[v]=min(st[v*2],st[v*2+1]);
        }
        void push(int v){
            st[v*2].f+=lz[v];
            lz[v*2]+=lz[v];
            st[v*2+1].f+=lz[v];
            lz[v*2+1]+=lz[v];
            lz[v]=0;
        }
        void update(int tl,int tr,int val,int l=0,int r=n-1,int v=1){
            if(r<tl or tr<l){
                return;
            }
            if(tl<=l and r<=tr){
                st[v].f+=val;
                lz[v]+=val;
                return;
            }
            push(v);
            int mid=(l+r)/2;
            update(tl,min(mid,tr),val,l,mid,v*2);
            update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
            st[v]=min(st[v*2],st[v*2+1]);
        }
        pair<int,int> query(int tl,int tr,int l=0,int r=n-1,int v=1){
            if(r<tl or tr<l){
                return {inf,-1};
            }
            if(tl<=l and r<=tr){
                return st[v];
            }
            push(v);
            int mid=(l+r)/2;
            return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
        }
        void add(int l,int r,int val){
            if(r<0){
                l+=n;
                r+=n;
            }
            if(l>=n){
                l-=n;
                r-=n;
            }
            if(l<0){
                l+=n;
                update(l,n-1,val);
                update(0,r,val);
            }
            else if(r>=n){
                r-=n;
                update(l,n-1,val);
                update(0,r,val);
            }
            else{
                update(l,r,val);
            }
        }
    };
    vector<int> ord,rev;
    vector<int> ord2,rev2;
}

void init(int k, std::vector<int> r) {
    int n=(int)r.size();
    {
        segtree T1(n);
        segtree T2(n);
        T1.init();
        T2.init();
        for(int i=0;i<n;i++){
            T1.update(i,i,r[i]);
            T2.update(i,i,inf);
        }
        for(int t=0;t<n;t++){
            while(T1.st[1].f==0){
                int i=T1.st[1].s;
                //cout<<"i "<<i<<'\n';
                T1.update(i,i,inf);
                T2.update(i,i,-inf);
                T2.add(i+1,i+k-1,1);
            }
            int pos=T2.st[1].s;
            //cout<<pos<<'\n';
            ord.push_back(pos);
            T2.update(pos,pos,inf);
            T2.add(pos+1,pos+k-1,-1);
            T1.add(pos-k+1,pos-1,-1);
        }
        rev.resize(n);
        for(int i=0;i<n;i++){
            rev[ord[i]]=i;
        }
    }
    {
        segtree2 T1(n);
        segtree2 T2(n);
        T1.init();
        T2.init();
        for(int i=0;i<n;i++){
            T1.update(i,i,r[i]);
            T2.update(i,i,inf);
        }
        for(int t=0;t<n;t++){
            while(T1.st[1].f==0){
                int i=-T1.st[1].s;
                //cout<<"i "<<i<<'\n';
                T1.update(i,i,inf);
                T2.update(i,i,-inf);
                T2.add(i+1,i+k-1,1);
            }
            int pos=-T2.st[1].s;
            //cout<<pos<<'\n';
            ord2.push_back(pos);
            T2.update(pos,pos,inf);
            T2.add(pos+1,pos+k-1,-1);
            T1.add(pos-k+1,pos-1,-1);
        }
        rev2.resize(n);
        for(int i=0;i<n;i++){
            rev2[ord2[i]]=i;
        }
    }
	return;
}

int compare_plants(int x, int y) {
    if(rev[x]<rev[y] and rev2[x]<rev2[y]) return 1;
    else if(rev[y]<rev[x] and rev2[y]<rev2[x]) 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