oj.uz

Submission #1041382

# Submission time Handle Problem Language Result Execution time Memory
1041382 2024-08-02T01:51:08 Z vjudge1 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 22864 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int n, pos[100100],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()){
        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);
    }
}
int compare_plants(int x, int y) {
    return pos[x]<pos[y]?1:-1;
}

Compilation message

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.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6820 KB Output is correct
7 Correct 30 ms 9648 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 31 ms 9652 KB Output is correct
11 Correct 29 ms 9564 KB Output is correct
12 Correct 32 ms 9724 KB Output is correct
13 Correct 29 ms 9552 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6820 KB Output is correct
7 Correct 30 ms 9648 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 31 ms 9652 KB Output is correct
11 Correct 29 ms 9564 KB Output is correct
12 Correct 32 ms 9724 KB Output is correct
13 Correct 29 ms 9552 KB Output is correct
14 Correct 45 ms 11856 KB Output is correct
15 Runtime error 43 ms 22864 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 28 ms 9636 KB Output is correct
4 Execution timed out 4078 ms 20564 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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