oj.uz

Submission #828710

# Submission time Handle Problem Language Result Execution time Memory
828710 2023-08-17T14:03:47 Z minhcool Comparing Plants (IOI20_plants) C++17
27 / 100
 297 ms 15692 KB 
//#define local
#ifndef local
#include "plants.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e9 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int a[N];
 
ii mini[N << 2];
int laz[N << 2];
 
void build(int id, int l, int r){
    if(l == r){
        mini[id] = {a[l], l};
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    mini[id] = min(mini[id << 1], mini[id << 1 | 1]);
}
 
void lazy(int id){
    int t = laz[id];
    if(!t) return;
    mini[id << 1].fi += t;
    mini[id << 1 | 1].fi += t;
    laz[id << 1] += t;
    laz[id << 1 | 1] += t;
    laz[id] = 0;
}
 
void upd(int id, int l, int r, int L, int R, int val){
    if(l > R || r < L || l > r) return;
    if(l >= L && r <= R){
        mini[id].fi += val;
        laz[id] += val;
        return;
    }
    lazy(id);
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, val);
    upd(id << 1 | 1, mid + 1, r, L, R, val);
    mini[id] = min(mini[id << 1], mini[id << 1 | 1]);
}
 
void er(int id, int l, int r, int pos){
    if(l == r){
        mini[id].fi = oo;
        return;
    }
    lazy(id);
    int mid = (l + r) >> 1;
    if(pos <= mid) er(id << 1, l, mid, pos);
    else er(id << 1 | 1, mid + 1, r, pos);
    mini[id] = min(mini[id << 1], mini[id << 1 | 1]);
}
 
ii get(int id, int l, int r, int L, int R){
    if(l > R || r < L) return {oo, oo};
    if(l >= L && r <= R) return mini[id];
    lazy(id);
    int mid = (l + r) >> 1;
    return min(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}
 
int b[N];
 
void init(int k, vector<int> r){
    k--;
    int n = r.size();
    for(int i = 0; i < n; i++) a[i] = k - r[i];
    build(1, 0, n - 1);
    for(int i = 0; i < n; i++){
        int temp = mini[1].se;
        ii temp2 = get(1, 0, n - 1, temp + k, n - 1);
        if(!temp2.fi) temp = temp2.se;
        if(temp == oo) assert(0);
        //cout << i << " " << temp << "\n";
        b[temp] = i;
        //cout << temp << " " << i << "\n";
        er(1, 0, n - 1, temp);
        //assert(get(1, 0, n - 1) == oo);
        upd(1, 0, n - 1, max(0, temp - k), temp - 1, -1);
        //cout << max(0, temp - k) << " " << temp - 1 << '\n';
        if(temp < k){
            upd(1, 0, n - 1, n + temp - k, n - 1, -1);
            //cout << n + temp - k << " " << n - 1 << "\n";
        }
    }
}
 
int compare_plants(int x, int y){
    if(b[x] < b[y]) return -1;
    if(b[x] > b[y]) return 1;
    return 0;
}
 
 
#ifdef local
void process(){
 
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 46 ms 5336 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 46 ms 5324 KB Output is correct
11 Correct 46 ms 5204 KB Output is correct
12 Correct 43 ms 5400 KB Output is correct
13 Correct 46 ms 5216 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 46 ms 5336 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 46 ms 5324 KB Output is correct
11 Correct 46 ms 5204 KB Output is correct
12 Correct 43 ms 5400 KB Output is correct
13 Correct 46 ms 5216 KB Output is correct
14 Correct 64 ms 6436 KB Output is correct
15 Correct 297 ms 15672 KB Output is correct
16 Correct 62 ms 6476 KB Output is correct
17 Correct 287 ms 15676 KB Output is correct
18 Correct 179 ms 15312 KB Output is correct
19 Correct 182 ms 15692 KB Output is correct
20 Correct 236 ms 15636 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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