oj.uz

Submission #1041623

# Submission time Handle Problem Language Result Execution time Memory
1041623 2024-08-02T06:26:06 Z vjudge1 Comparing Plants (IOI20_plants) C++17
59 / 100
 548 ms 68176 KB 
#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;
int bjl[200100][20],bjr[200100][20], gooverL[200100], gooverR[200100];
struct segtree{
    pair<int,int> T[1<<19];
    int lz[1<<20];
    inline 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;
inline int AGL(int k){
    return (k+n)%n;
}
inline 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);
}
inline 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);
}
inline 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()){
        int bst=(--gaps.end())->second;
        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);
        while(possiblemin());
        del(bst);
    }
    set<pair<int,int>> st;
    st.insert({1e9,n});
    for(int i=n-k;i<n;i++)
        st.insert({pos[i],i});
    for(int i=0;i<n;i++)bjl[i][0]=st.upper_bound({pos[i],0})->second,
        st.erase({pos[(i+n-k)%n],(i+n-k)%n}),st.insert({pos[i],i});
    st.clear();
    for(int i=0;i<k;i++)
        st.insert({pos[i],i});
    st.insert({1e9,n});
    bjl[n][0]=bjr[n][0]=n;
    for(int i=n;i--;)bjr[i][0]=st.upper_bound({pos[i],0})->second,
        st.erase({pos[(i+k)%n],(i+k)%n}),st.insert({pos[i],i});
    for(int i=0;i<n;i++)
        if(bjl[i][0]>i&&bjl[i][0]-n)
            gooverL[i]=bjl[i][0],bjl[i][0]=i;
    for(int i=0;i<n;i++)
        if(bjr[i][0]<i&&bjr[i][0]-n)
            gooverR[i]=bjr[i][0],bjr[i][0]=i;
    for(int j=1;j<20;j++) for(int i=0;i<=n;i++)
        bjl[i][j]=bjl[bjl[i][j-1]][j-1],
        bjr[i][j]=bjr[bjr[i][j-1]][j-1];
    pos[n]=1e9;
}
int biggerl(int x,int y){
    int prevx=x;
    if(x<y)x=gooverL[bjl[x][19]];
    if(x<=y) return pos[bjl[prevx][19]]<=pos[y];
    for(int i=20;i--;)
        if(bjl[x][i]>y&&bjl[x][i]-n)
            x=bjl[x][i];
    if(bjl[x][0]==n)
        return 0;
    return pos[x]<=pos[y];
}
int biggerr(int x,int y){
    int prevx=x;
    if(x>y)x=gooverR[bjr[x][19]];
    if(x>=y) return pos[bjr[prevx][19]]<=pos[y];
    for(int i=20;i--;)
        if(bjr[x][i]<y&&bjr[x][i]-n)
            x=bjr[x][i];
    if(bjr[x][0]==n)
        return 0;
    return pos[x]<=pos[y];
}
inline int bigger(int x,int y){
    return biggerl(x,y)||biggerr(x,y);
}
int compare_plants(int x, int y) {
    if(pos[x]<pos[y])
        return bigger(x,y)?1:0;
    return bigger(y,x)?-1:0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Incorrect 1 ms 10844 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 4 ms 12888 KB Output is correct
7 Correct 43 ms 17704 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 43 ms 17816 KB Output is correct
11 Correct 52 ms 15632 KB Output is correct
12 Correct 50 ms 17748 KB Output is correct
13 Correct 42 ms 17744 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 4 ms 12888 KB Output is correct
7 Correct 43 ms 17704 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 43 ms 17816 KB Output is correct
11 Correct 52 ms 15632 KB Output is correct
12 Correct 50 ms 17748 KB Output is correct
13 Correct 42 ms 17744 KB Output is correct
14 Correct 72 ms 24596 KB Output is correct
15 Correct 544 ms 56404 KB Output is correct
16 Correct 71 ms 24656 KB Output is correct
17 Correct 547 ms 56312 KB Output is correct
18 Correct 461 ms 59476 KB Output is correct
19 Correct 303 ms 55380 KB Output is correct
20 Correct 545 ms 59984 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 12892 KB Output is correct
3 Correct 47 ms 17344 KB Output is correct
4 Correct 290 ms 56124 KB Output is correct
5 Correct 353 ms 51284 KB Output is correct
6 Correct 356 ms 50256 KB Output is correct
7 Correct 436 ms 50924 KB Output is correct
8 Correct 548 ms 54868 KB Output is correct
9 Correct 308 ms 54612 KB Output is correct
10 Correct 312 ms 51540 KB Output is correct
11 Correct 368 ms 68176 KB Output is correct
12 Correct 210 ms 50004 KB Output is correct
13 Correct 456 ms 63056 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Incorrect 1 ms 12892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 12892 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 334 ms 49404 KB Output is correct
7 Correct 375 ms 49388 KB Output is correct
8 Correct 415 ms 50000 KB Output is correct
9 Correct 527 ms 53856 KB Output is correct
10 Correct 301 ms 53772 KB Output is correct
11 Correct 392 ms 53328 KB Output is correct
12 Correct 266 ms 55124 KB Output is correct
13 Correct 315 ms 50556 KB Output is correct
14 Correct 353 ms 49488 KB Output is correct
15 Correct 397 ms 50256 KB Output is correct
16 Correct 293 ms 52052 KB Output is correct
17 Correct 327 ms 49744 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Incorrect 1 ms 10844 KB Output isn't correct
6 Halted 0 ms 0 KB -