oj.uz

Submission #1015548

# Submission time Handle Problem Language Result Execution time Memory
1015548 2024-07-06T13:54:33 Z gaurezzz Comparing Plants (IOI20_plants) C++17
27 / 100
 484 ms 42528 KB 
#include <bits/stdc++.h>
 
#define F first 
#define S second
#define ll long long
#define nd '\n'
 
using namespace std;
 
vector <long long> plants;
vector <ll> finale;
ll k;
ll n;
struct nodo {
 
    ll limIz, limDe;
    ll lazy=0;
    ll v;
    ll medio;
    ll minimo;
    ll posMinimo;
    nodo *left, *right;
 
    nodo(ll iz, ll de){ limIz = iz, limDe = de;}
 
    void build (){
 
        if (limIz == limDe){
            v = plants[limIz];
            minimo = v;
            posMinimo = limIz;
            return;
        }
 
        medio = (limDe+limIz)/2;
 
        left = new nodo(limIz, medio);
        right = new nodo(medio+1, limDe);
 
        left->build();
        right->build();
 
        v = left->v + right-> v;
        if (left->minimo <= right->minimo)
        minimo = left->minimo, posMinimo = left->posMinimo;
        else minimo = right->minimo, posMinimo = right->posMinimo;
 
        //cout << "nodo: " << limIz << " " << limDe << nd;
        //cout << "v: " << v << " minimo: " << minimo << " pos: " << posMinimo<< nd;
    }
 
    void updateLazy(){
 
        if (lazy == 0) return;
 
        v+=(limDe-limIz+1)*lazy;
        minimo+=lazy;
 
        //cout << "lazy " << lazy << " min " << minimo << nd;
 
        if (limIz != limDe) left->lazy+=lazy, right->lazy+=lazy;
 
        lazy=0;
    }
 
    void update (ll upL, ll upR, ll v){
 
        //cout << limIz << " entrandou " << limDe << nd;
        updateLazy();
 
        if (upL <= limIz && limDe <= upR){
            lazy+=v;
            //cout << limIz << " laziando " << limDe << nd;
            updateLazy();
            return;
        }
 
        if (limIz > upR || limDe < upL) return;
 
        left->update(upL, upR, v);
        right->update(upL, upR, v);
 
        v = left->v + right->v;
        if (left->minimo <= right->minimo)
        minimo = left->minimo, posMinimo = left->posMinimo;
        else minimo = right->minimo, posMinimo = right->posMinimo;
 
        //cout << "nodo: " << limIz << " " << limDe << nd;
        //cout << "v: " << v << " minimo: " << minimo << nd;
    }
 
    pair <ll,ll> query (ll qL, ll qR){
 
        //cout << limIz << " entrando " << limDe << nd;
        //cout << lazy << nd;
 
        updateLazy();
 
        if (qL <= limIz && limDe <= qR){
            //cout << "query: " << limIz << " " << limDe << nd;
            //cout << minimo << " x " << posMinimo << nd;
            return {minimo, posMinimo};
        }
 
        if (limIz > qR || limDe < qL) return {(long long) INT_MAX, -1};
 
        pair <ll,ll> a = left->query(qL, qR);
        pair <ll,ll> b = right->query(qL, qR);
 
        //cout << "query: " << limIz << " " << limDe << nd;
        //cout << a.F << " " << a.S << " " << b.F << " " << b.S << nd; 
 
        if (a.F <= b.F) return a;
        else return b;
    }
};
 
pair<ll,ll> procesarConsulta(long long l, long long r, nodo *st){
 
    //cout << l << " " << r << nd;
 
    if (l <= r) return st->query(l, r-1);
    
    pair <ll,ll> a = st->query(l, n-1);
 
    if (r == 0) return a;
 
    pair <ll,ll> b = st->query(0, r-1);
 
    if (a.F <= b.F) return a;
    else return b;
}
 
void procesarUpdate(long long l, long long r, nodo *st){
 
    //cout << "actualizando" << l << " " << r << nd;
 
    if (l <= r){ st->update(l, r-1, -1); return;}
    
    st->update(l, n-1, -1);
 
    if (r == 0) return;
 
    st->update(0, r-1, -1);
}
 
nodo *st;
 
void init (int K, vector <int> r){
 
	for (auto x: r) plants.push_back(x);
 
    k=K;
 
    n = r.size();
 
    st = new nodo(0, n-1);
 
    st->build();

    //vector <pair <ll,ll>> s;
 
      //  for (ll j=0; j<n; j++) {
        //    s.push_back(st->query(j,j));
        //}
        //for (ll j=0; j<n; j++) {
          //  cout << s[j].F << " ";
       // }
        //cout << nd;
 
    finale.assign(n,1);
    ll orden=0;
 
    pair <ll,ll> cero = st->query(0, n-1);
 
    //cout << 1 << nd;
 
    auto posible = procesarConsulta((cero.S-k+1+n)%n, cero.S, st);
 
    //cout << "posible  " << posible.F << " " << posible.S << nd;
 
    if (posible.F == 0) cero = posible;
 
    for (ll i=0; i<n; i++){
 
        //cout << i << nd;
 
        procesarUpdate((cero.S-k+1+n)%n, cero.S, st);
        //cout << "aaa" << nd;
        st->update(cero.S, cero.S, (long long)INT_MAX);
 
        finale[cero.S] = orden--;
 
        //vector <pair <ll,ll>> s;
 
        //for (ll j=0; j<n; j++) {
          //  s.push_back(st->query(j,j));
        //}
        //for (ll j=0; j<n; j++) {
          //  cout << s[j].F << " ";
        //}
        //cout << nd;
 
        //for (ll j=0; j<n; j++) cout << finale[j] << " ";
    //cout << nd;
 
        if (i == n-1) break;
        cero = procesarConsulta((cero.S-k+1+n)%n, cero.S, st);
        if (cero.F != 0) cero = st->query(0, n-1);
        auto posible = procesarConsulta((cero.S-k+1+n)%n, cero.S, st);
        //cout << cero.S << " ceros " << posible.S << nd;
        if (posible.F == 0) cero = posible;

    }
}
 
int compare_plants(int x, int y){
 
	if (finale[x] > finale[y]) return 1;
    else return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 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 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 38 ms 6000 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 41 ms 5968 KB Output is correct
11 Correct 59 ms 5736 KB Output is correct
12 Correct 34 ms 5968 KB Output is correct
13 Correct 37 ms 5832 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 38 ms 6000 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 41 ms 5968 KB Output is correct
11 Correct 59 ms 5736 KB Output is correct
12 Correct 34 ms 5968 KB Output is correct
13 Correct 37 ms 5832 KB Output is correct
14 Correct 63 ms 8912 KB Output is correct
15 Correct 469 ms 42432 KB Output is correct
16 Correct 62 ms 8944 KB Output is correct
17 Correct 484 ms 42528 KB Output is correct
18 Correct 206 ms 41920 KB Output is correct
19 Correct 228 ms 42436 KB Output is correct
20 Correct 365 ms 42436 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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