oj.uz

답안 #1041400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041400 2024-08-02T02:50:51 Z vjudge1 식물 비교 (IOI20_plants) C++17
44 / 100
 318 ms 32336 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()){
        vector<int>stuff;
        auto it=gaps.rbegin();
        while(it!=gaps.rend()&&it->first>k)
            stuff.push_back(it++->second);
        if(gaps.size()==1)
            stuff={*CD.begin()};
        assert(stuff.size());
        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

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 6744 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 6540 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 34 ms 9648 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 35 ms 9640 KB Output is correct
11 Correct 30 ms 9552 KB Output is correct
12 Correct 28 ms 9556 KB Output is correct
13 Correct 30 ms 9556 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 6540 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 34 ms 9648 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 35 ms 9640 KB Output is correct
11 Correct 30 ms 9552 KB Output is correct
12 Correct 28 ms 9556 KB Output is correct
13 Correct 30 ms 9556 KB Output is correct
14 Correct 46 ms 11860 KB Output is correct
15 Correct 209 ms 13904 KB Output is correct
16 Correct 47 ms 11856 KB Output is correct
17 Correct 218 ms 14248 KB Output is correct
18 Correct 307 ms 23284 KB Output is correct
19 Correct 117 ms 13984 KB Output is correct
20 Correct 204 ms 13908 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 6748 KB Output is correct
3 Correct 31 ms 9628 KB Output is correct
4 Correct 191 ms 20308 KB Output is correct
5 Correct 247 ms 15444 KB Output is correct
6 Correct 263 ms 14264 KB Output is correct
7 Correct 247 ms 13916 KB Output is correct
8 Correct 227 ms 14160 KB Output is correct
9 Correct 281 ms 18772 KB Output is correct
10 Correct 258 ms 15952 KB Output is correct
11 Correct 290 ms 32336 KB Output is correct
12 Correct 102 ms 13948 KB Output is correct
13 Correct 318 ms 27248 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 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -