Submission #1178472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178472		guagua0407	식물 비교 (IOI20_plants)	C++20	44 / 100	582 ms	24808 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;
        segtree2(int _n){
            n=_n;
            st=vector<pair<int,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 update(int pos,int val,int l=0,int r=n-1,int v=1){
            if(l==r){
                st[v].f=val;
                return;
            }
            int mid=(l+r)/2;
            if(pos<=mid) update(pos,val,l,mid,v*2);
            else update(pos,val,mid+1,r,v*2+1);
            st[v]=max(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];
            }
            int mid=(l+r)/2;
            return max(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
        }
        int query(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;
}

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 T3(n);
    T3.init();
    for(int t=n-1;t>=0;t--){

    }*/
	return;
}

int compare_plants(int x, int y) {
    if(rev[x]<rev[y]) return 1;
    else return -1;
    return 0;
}

Compilation message (stderr)

plants.cpp: In member function 'int {anonymous}::segtree2::query(int, int, int)':
plants.cpp:148:9: warning: no return statement in function returning non-void [-Wreturn-type]
  148 |         }
      |         ^

• 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