oj.uz

Submission #357733

# Submission time Handle Problem Language Result Execution time Memory
357733 2021-01-24T14:34:16 Z doowey Comparing Plants (IOI20_plants) C++14
44 / 100
 1625 ms 28524 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;
        push(node, cl, cr);
        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, int ta){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return mp((int)1e9, (int)1e9);
    if(cl >= tl && cr <= tr){
        if(ta == 0)
            return T[node].zero;
        else
            return T[node].valid;
    }
    int mid = (cl + cr) / 2;
    return min(get(node * 2, cl, mid, tl, tr, ta), get(node * 2 + 1, mid + 1, cr, tl, tr, ta));
}

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, 0);
        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:123:9: warning: unused variable 'nx' [-Wunused-variable]
  123 |     int nx;
      |         ^~

Subtask #1
0 / 5.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 14 ms 19180 KB Output is correct
4 Incorrect 11 ms 19204 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 10 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 Correct 12 ms 19180 KB Output is correct
5 Correct 13 ms 19180 KB Output is correct
6 Correct 19 ms 19308 KB Output is correct
7 Correct 106 ms 23916 KB Output is correct
8 Correct 12 ms 19180 KB Output is correct
9 Correct 16 ms 19308 KB Output is correct
10 Correct 95 ms 23916 KB Output is correct
11 Correct 90 ms 23916 KB Output is correct
12 Correct 88 ms 24044 KB Output is correct
13 Correct 95 ms 23916 KB Output is correct

Subtask #3
13.0 / 13.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 Correct 11 ms 19180 KB Output is correct
4 Correct 12 ms 19180 KB Output is correct
5 Correct 13 ms 19180 KB Output is correct
6 Correct 19 ms 19308 KB Output is correct
7 Correct 106 ms 23916 KB Output is correct
8 Correct 12 ms 19180 KB Output is correct
9 Correct 16 ms 19308 KB Output is correct
10 Correct 95 ms 23916 KB Output is correct
11 Correct 90 ms 23916 KB Output is correct
12 Correct 88 ms 24044 KB Output is correct
13 Correct 95 ms 23916 KB Output is correct
14 Correct 183 ms 24556 KB Output is correct
15 Correct 1625 ms 26860 KB Output is correct
16 Correct 190 ms 24556 KB Output is correct
17 Correct 1604 ms 28524 KB Output is correct
18 Correct 1114 ms 28044 KB Output is correct
19 Correct 1060 ms 28524 KB Output is correct
20 Correct 1513 ms 28472 KB Output is correct

Subtask #4
17.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 Correct 76 ms 21996 KB Output is correct
4 Correct 866 ms 26988 KB Output is correct
5 Correct 1012 ms 28012 KB Output is correct
6 Correct 1293 ms 28012 KB Output is correct
7 Correct 1521 ms 28140 KB Output is correct
8 Correct 1617 ms 28396 KB Output is correct
9 Correct 909 ms 27628 KB Output is correct
10 Correct 920 ms 27756 KB Output is correct
11 Correct 636 ms 27628 KB Output is correct
12 Correct 806 ms 27956 KB Output is correct
13 Correct 1063 ms 27884 KB Output is correct

Subtask #5
0 / 11.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 10 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 11 ms 19180 KB Output is correct
2 Correct 11 ms 19180 KB Output is correct
3 Incorrect 10 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 10 ms 19180 KB Output is correct
3 Correct 14 ms 19180 KB Output is correct
4 Incorrect 11 ms 19204 KB Output isn't correct
5 Halted 0 ms 0 KB -