Submission #1041396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041396		vjudge1	Comparing Plants (IOI20_plants)	C++17	0 / 100	4099 ms	7000 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int n, pos[200100],CA;
vector<int> R;
set<int> CD;
set<pair<int,int>> gaps;
struct segtree{
    pair<int,int> T[1<<19];
    int lz[1<<20];
    void pd(int i){
        if(lz[i]){
            T[i].first+=lz[i];
            lz[i*2]+=lz[i];
            lz[i*2+1]+=lz[i];
            lz[i]=0;
        }
    }
    void init(int i,int l,int r){
        if(l==r)return void(T[i]={R[l],l});
        init(i*2,l,l+r>>1);
        init(i*2+1,l+r+2>>1,r);
        T[i]=min(T[i*2],T[i*2+1]);
    }
    void upd(int i,int l,int r,int ll,int rr){
        pd(i);if(ll<=l&&r<=rr)
            return lz[i]=-1,pd(i);
        if(l>rr||ll>r)return;
        upd(i*2,l,l+r>>1,ll,rr);
        upd(i*2+1,l+r+2>>1,r,ll,rr);
        T[i]=min(T[i*2],T[i*2+1]);
    }
    void upd2(int i,int l,int r,int ll,int rr){
        pd(i);if(ll<=l&&r<=rr)
            return lz[i]=1e9,pd(i);
        if(l>rr||ll>r)return;
        upd2(i*2,l,l+r>>1,ll,rr);
        upd2(i*2+1,l+r+2>>1,r,ll,rr);
        T[i]=min(T[i*2],T[i*2+1]);
    }
}ST;
int AGL(int k){
    return (k+n)%n;
}
void add(int i){
    if(!CD.size()){
        gaps.insert({n,i});
        CD.insert(i);
        return;
    }
    if(CD.size()==1){
        CD.insert(i);
        gaps.clear();
        int a=*CD.begin();
        int b=*--CD.end();
        gaps.insert({b-a,b});
        gaps.insert({n+a-b,a});
        return;
    }
    auto it1=CD.upper_bound(i);
    auto it2=it1;
    if(it2==CD.begin())
        it2=--CD.end();
    else --it2;
    if(it1==CD.end())
        it1=CD.begin();
    gaps.insert({AGL(i-*it2),i});
    gaps.insert({AGL(*it1-i),*it1});
    gaps.erase({AGL(*it1-*it2),*it1});
    CD.insert(i);
}
void del(int i){
    if(CD.size()==1)
        return CD.clear(),gaps.clear();
    else if(CD.size()==2){
        CD.erase(i);
        gaps.clear();
        gaps.insert({n,*CD.begin()});
        return;
    }
    auto it1=CD.upper_bound(i);
    auto it2=CD.find(i);
    if(it2==CD.begin())
        it2=--CD.end();
    else --it2;
    if(it1==CD.end())
        it1=CD.begin();
    gaps.erase({AGL(i-*it2),i});
    gaps.erase({AGL(*it1-i),*it1});
    gaps.insert({AGL(*it1-*it2),*it1});
    CD.erase(i);
}
int possiblemin(){
    auto[a,b]=ST.T[1];
    if(!a) {
        ST.upd2(1,0,n-1,b,b);
        add(b);
        return 1;
    }
    return 0;
}
void init(int k, std::vector<int> r) {
    R=r;
    k--;
    n=r.size();
    ST.init(1,0,n-1);
    while(possiblemin());
    while(CD.size()){
        assert(gaps.size());
        vector<int>stuff;
        auto it=gaps.begin();
        while(it!=gaps.end()&&it->first>k)
            stuff.push_back(it++->second);
        for(auto bst: stuff) {
            pos[bst]=CA;
            if(bst<k)ST.upd(1,0,n-1,0,bst),
                ST.upd(1,0,n-1,bst-k+n,n-1);
            else ST.upd(1,0,n-1,bst-k,bst);
            del(bst);
        }
        while(possiblemin());
        CA++;
    }
}
int compare_plants(int x, int y) {
    if(pos[x]==pos[y])return 0;
    return pos[x]<pos[y]?1:-1;
}

Compilation message (stderr)

plants.cpp: In member function 'void segtree::init(int, int, int)':
plants.cpp:21:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         init(i*2,l,l+r>>1);
      |                    ~^~
plants.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         init(i*2+1,l+r+2>>1,r);
      |                    ~~~^~
plants.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
plants.cpp:29:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         upd(i*2,l,l+r>>1,ll,rr);
      |                   ~^~
plants.cpp:30:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         upd(i*2+1,l+r+2>>1,r,ll,rr);
      |                   ~~~^~
plants.cpp: In member function 'void segtree::upd2(int, int, int, int, int)':
plants.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         upd2(i*2,l,l+r>>1,ll,rr);
      |                    ~^~
plants.cpp:38:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         upd2(i*2+1,l+r+2>>1,r,ll,rr);
      |                    ~~~^~

• 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