oj.uz

Submission #1080245

# Submission time Handle Problem Language Result Execution time Memory
1080245 2024-08-29T08:18:10 Z GrindMachine Comparing Plants (IOI20_plants) C++17
44 / 100
 320 ms 39148 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; ++i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
    return "'"+s+"'";
}

string to_string(const char* s){
    return to_string((string)s);
}

string to_string(bool b){
    return b?"true":"false";
}

template<typename A>
string to_string(A v){
    string res = "{";
    trav(x,v){
        res += to_string(x)+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
    return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1<<18;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "plants.h"

pii d_neutral = {inf1,-1};
vector<pii> tr(4*N,d_neutral);
vector<int> lz(4*N);

void propagate(int x, int lx, int rx){
    int v = lz[x];
    tr[x].ff += v;

    if(rx-lx > 1){
        lz[x<<1] += v;
        lz[x<<1|1] += v;
    }

    lz[x] = 0;
}

void rupd(int x, int lx, int rx, int l, int r, int v){
    propagate(x,lx,rx);

    if(lx >= r or rx <= l) return;
    if(lx >= l and rx <= r){
        lz[x] = v;
        propagate(x,lx,rx);
        return;
    }

    int mid = (lx+rx)>>1;
    rupd(x<<1,lx,mid,l,r,v);
    rupd(x<<1|1,mid,rx,l,r,v);

    tr[x] = min(tr[x<<1],tr[x<<1|1]);
}

void rupd(int l, int r, int v){
    rupd(1,0,N,l,r+1,v);
}

pii query(){
    propagate(1,0,N);
    return tr[1];
}

void build(int x, int lx, int rx, vector<int> &a){
    if(rx-lx == 1){
        if(lx < sz(a)){
            tr[x] = {a[lx],lx};
        }
        return;
    }

    int mid = (lx+rx) >> 1;
    build(x<<1,lx,mid,a);
    build(x<<1|1,mid,rx,a);
    tr[x] = min(tr[x<<1],tr[x<<1|1]);
}

void build(vector<int> &a){
    build(1,0,N,a);
}

vector<int> id(N);

void init(int k, std::vector<int> a) {
    k--;
    int n = sz(a);
    build(a);

    int iter = 0;
    int rem_cnt = 0;

    auto rem = [&](int i){
        rem_cnt++;
        if(i-k >= 0){
            rupd(i-k,i-1,-1);
        }
        else{
            rupd(0,i-1,-1);
            rupd(i-k+n,n-1,-1);
        }
    };

    set<int> zeros;
    set<pii> dis;

    while(rem_cnt < n){
        iter++;

        while(true){
            auto [mn,i] = query();
            if(mn == 0){
                rupd(i,i,inf1);

                zeros.insert(i);
                auto it = zeros.find(i);
                int prevv = -1, nxt = -1;
                if(it != zeros.begin()){
                    prevv = *prev(it);
                }
                if(next(it) != zeros.end()){
                    nxt = *next(it);
                }

                if(prevv != -1 and nxt != -1) dis.erase({nxt-prevv,nxt});
                if(prevv != -1) dis.insert({i-prevv,i});
                if(nxt != -1) dis.insert({nxt-i,nxt});
            }
            else{
                break;
            }
        }


        // debug(zeros);
        // debug(dis);
        // debug(del);

        if(sz(zeros) == 1){
            trav(i,zeros){
                rem(i);
                id[i] = iter;
            }

            zeros.clear();
            dis.clear();
            conts;
        }

        vector<int> del;

        {
            int i = *zeros.begin(), j = *zeros.rbegin();
            int d = (i-j+n)%n;
            if(d > k){
                del.pb(i);
            }            
        }

        for(auto it = dis.rbegin(); it != dis.rend(); ++it){
            auto [d,i] = *it;
            if(d > k){
                del.pb(i);
            }
            else{
                break;
            }
        }

        trav(i,del){
            rem(i);
            id[i] = iter;

            auto it = zeros.find(i);
            int prevv = -1, nxt = -1;
            if(it != zeros.begin()){
                prevv = *prev(it);
            }
            if(next(it) != zeros.end()){
                nxt = *next(it);
            }

            zeros.erase(it);

            if(prevv != -1) dis.erase({i-prevv,i});
            if(nxt != -1) dis.erase({nxt-i,nxt});
            if(prevv != -1 and nxt != -1) dis.insert({nxt-prevv,nxt});
        }
    }
}

int compare_plants(int x, int y) {
    if(id[x] < id[y]) return 1;
    if(id[x] > id[y]) return -1;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13660 KB Output is correct
2 Correct 6 ms 13800 KB Output is correct
3 Correct 7 ms 13660 KB Output is correct
4 Incorrect 7 ms 13660 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 7 ms 13660 KB Output is correct
2 Correct 7 ms 13744 KB Output is correct
3 Correct 6 ms 13660 KB Output is correct
4 Correct 6 ms 13660 KB Output is correct
5 Correct 7 ms 13656 KB Output is correct
6 Correct 9 ms 13656 KB Output is correct
7 Correct 48 ms 17268 KB Output is correct
8 Correct 8 ms 13656 KB Output is correct
9 Correct 8 ms 13660 KB Output is correct
10 Correct 47 ms 17272 KB Output is correct
11 Correct 42 ms 17372 KB Output is correct
12 Correct 40 ms 17284 KB Output is correct
13 Correct 44 ms 17064 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13660 KB Output is correct
2 Correct 7 ms 13744 KB Output is correct
3 Correct 6 ms 13660 KB Output is correct
4 Correct 6 ms 13660 KB Output is correct
5 Correct 7 ms 13656 KB Output is correct
6 Correct 9 ms 13656 KB Output is correct
7 Correct 48 ms 17268 KB Output is correct
8 Correct 8 ms 13656 KB Output is correct
9 Correct 8 ms 13660 KB Output is correct
10 Correct 47 ms 17272 KB Output is correct
11 Correct 42 ms 17372 KB Output is correct
12 Correct 40 ms 17284 KB Output is correct
13 Correct 44 ms 17064 KB Output is correct
14 Correct 65 ms 17488 KB Output is correct
15 Correct 290 ms 19280 KB Output is correct
16 Correct 64 ms 16720 KB Output is correct
17 Correct 264 ms 17696 KB Output is correct
18 Correct 304 ms 26964 KB Output is correct
19 Correct 179 ms 21328 KB Output is correct
20 Correct 281 ms 21264 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13660 KB Output is correct
2 Correct 6 ms 13688 KB Output is correct
3 Correct 42 ms 17220 KB Output is correct
4 Correct 251 ms 24848 KB Output is correct
5 Correct 303 ms 22376 KB Output is correct
6 Correct 304 ms 21116 KB Output is correct
7 Correct 302 ms 21232 KB Output is correct
8 Correct 272 ms 21228 KB Output is correct
9 Correct 320 ms 25368 KB Output is correct
10 Correct 254 ms 22608 KB Output is correct
11 Correct 244 ms 39148 KB Output is correct
12 Correct 135 ms 20628 KB Output is correct
13 Correct 291 ms 33804 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13660 KB Output is correct
2 Correct 8 ms 13612 KB Output is correct
3 Incorrect 7 ms 13660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13800 KB Output is correct
2 Correct 7 ms 13660 KB Output is correct
3 Incorrect 6 ms 13656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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