oj.uz

답안 #1041383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041383 2024-08-02T01:51:33 Z vjudge1 식물 비교 (IOI20_plants) C++17
44 / 100
 308 ms 35412 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;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 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 6832 KB Output is correct
7 Correct 30 ms 9564 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 30 ms 9652 KB Output is correct
11 Correct 30 ms 9564 KB Output is correct
12 Correct 32 ms 9564 KB Output is correct
13 Correct 30 ms 9664 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 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 6832 KB Output is correct
7 Correct 30 ms 9564 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 30 ms 9652 KB Output is correct
11 Correct 30 ms 9564 KB Output is correct
12 Correct 32 ms 9564 KB Output is correct
13 Correct 30 ms 9664 KB Output is correct
14 Correct 46 ms 11856 KB Output is correct
15 Correct 224 ms 13916 KB Output is correct
16 Correct 48 ms 13912 KB Output is correct
17 Correct 223 ms 17816 KB Output is correct
18 Correct 308 ms 26708 KB Output is correct
19 Correct 145 ms 17748 KB Output is correct
20 Correct 194 ms 17748 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6724 KB Output is correct
3 Correct 28 ms 9556 KB Output is correct
4 Correct 201 ms 20356 KB Output is correct
5 Correct 245 ms 18516 KB Output is correct
6 Correct 244 ms 17492 KB Output is correct
7 Correct 247 ms 17600 KB Output is correct
8 Correct 230 ms 17748 KB Output is correct
9 Correct 238 ms 21656 KB Output is correct
10 Correct 222 ms 18504 KB Output is correct
11 Correct 293 ms 35412 KB Output is correct
12 Correct 111 ms 17232 KB Output is correct
13 Correct 297 ms 30288 KB Output is correct

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 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 #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 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 -