oj.uz

Submission #357722

# Submission time Handle Problem Language Result Execution time Memory
357722 2021-01-24T13:51:31 Z doowey Comparing Plants (IOI20_plants) C++14
0 / 100
 76 ms 22764 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

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

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 100;
int A[N];
int vl[N];

struct Node{
    pii valid; // = r + vl
    pii zero; // = r
    int rlazy;
    int vllazy;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    T[node].valid.fi += T[node].rlazy + T[node].vllazy;
    T[node].zero.fi += T[node].rlazy;
    if(cl != cr){
        T[node*2].rlazy += T[node].rlazy;
        T[node*2+1].rlazy += T[node].rlazy;
        T[node*2].vllazy += T[node].vllazy;
        T[node*2+1].vllazy += T[node].vllazy;
    }
    T[node].rlazy = 0;
    T[node].vllazy = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, int typ, int v){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        if(typ == 0) T[node].rlazy = v;
        else T[node].vllazy = v;
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, typ, v);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, typ, v);
    T[node].valid = min(T[node*2].valid, T[node*2+1].valid);
    T[node].zero = min(T[node*2].zero, T[node*2+1].zero);

}

pii get(int node, int cl, int cr, int tl, int tr){
    if(tl > tr) return mp((int)1e9, (int)1e9);
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return mp((int)1e9, (int)1e9);
    if(cl >= tl && cr <= tr){
        return T[node].zero;
    }
    int mid = (cl + cr) / 2;
    return min(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
}

vector<int> r;

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node].valid = mp(r[cl], cl);
        T[node].zero = mp(r[cl], cl);
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node].valid = min(T[node * 2].valid, T[node * 2 + 1].valid);
    T[node].zero = min(T[node * 2].zero, T[node * 2 + 1].zero);
}

int n, k;

void upd_zero(int ii, int sign){
    int nx = (ii + k - 1) % n;
    if(nx > ii){
        upd(1, 0, n - 1, ii + 1, nx, 1, sign);
    }
    else{
        upd(1, 0, n - 1, ii + 1, n - 1, 1, sign);
        upd(1, 0, n - 1, 0, nx, 1, sign);
    }
}

vector<int> getz(int li, int ri){
    vector<int> soln;
    pii cc;
    while(li < ri){
        cc = get(1, 0, n - 1, li, ri);
        if(cc.fi != 0) return soln;
        soln.push_back(cc.se);
        li = cc.se + 1;
    }
    return soln;
}

void init(int k_, vector<int> r_) {
    r = r_;
    k = k_;
    n = r.size();
    build(1, 0, n - 1);
    for(int i = 0 ; i < n; i ++ ){
        if(r[i] == 0){
            upd_zero(i,+1);
        }
    }

    int st;
    int pv;
    int nx;
    for(int id = n - 1; id >= 0 ; id -- ){
        st = T[1].valid.se;
        A[st] = id;
        pv = (st - (k - 1) + n) % n;
        upd(1, 0, n - 1, st, st, 0, (int)1e9);
        upd_zero(st,-1);
        vector<int> nwz, cc;
        if(pv < st){
            upd(1, 0, n - 1, pv, st - 1, 0, -1);
            cc = getz(pv, st - 1);
            for(auto q : cc) nwz.push_back(q);
        }
        else{
            upd(1, 0, n - 1, 0, st - 1, 0, -1);
            upd(1, 0, n - 1, pv, n - 1, 0, -1);
            cc = getz(0, st - 1);
            for(auto q : cc) nwz.push_back(q);
            cc = getz(pv, n - 1);
            for(auto q : cc) nwz.push_back(q);
        }
        for(auto x : nwz){
            upd_zero(x,+1);
        }
    }
}

int compare_plants(int x, int y) {
    if(A[x] < A[y]) return -1;
    return +1;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:121:9: warning: unused variable 'nx' [-Wunused-variable]
  121 |     int nx;
      |         ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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