oj.uz

Submission #814839

# Submission time Handle Problem Language Result Execution time Memory
814839 2023-08-08T10:28:30 Z vjudge1 Comparing Plants (IOI20_plants) C++17
27 / 100
 416 ms 17108 KB 
#include "plants.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
int N, K;
vi arr;
const int MAX = 200100;
struct seg_tree{
	pii tree[4*MAX];
    int lazy[4*MAX];
    void init(int node, int l, int r) {
        if(l == r) {
            tree[node].second=l;
            return;
        }
        int m = (l + r) / 2;
        init(node*2, l, m);
        init(node*2+1, m+1, r);
        tree[node]=min(tree[node*2], tree[node*2+1]);
    }
    void lazy_prop(int node, int s, int e) {
        tree[node].first+=lazy[node];
        if(s!=e) {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    void update(int node, int s, int e, int l, int r, int v) {
        lazy_prop(node, s, e);
        if(s>r || e<l) return;
        if(s>=l && e<=r) {
            lazy[node]+=v;
            lazy_prop(node, s, e);
            return;
        }
        int m = (s + e) / 2;
        update(node*2, s, m, l, r, v);
        update(node*2+1, m+1, e, l, r, v);
        tree[node]=min(tree[node*2], tree[node*2+1]);
    }
    pair<int, int> query(int node, int s, int e, int l, int r) {
        lazy_prop(node, s, e);
        if(s>r || e<l) return make_pair(1e9, 0);
        if(s>=l && e<=r) return tree[node];
  
        int m = (s + e) / 2;
        return min(query(node*2, s, m, l, r), query(node*2+1, m+1, e, l, r));
    }
} tree;
vi a;
void init(int k, vector<int> r) {
	N = (int)r.size();
	a.resize(N);
	tree.init(1, 0, N-1);
	for(int i = 0; i < N; i++)	tree.update(1, 0, N-1, i, i, r[i]);
	for(int i=0; i<N; i++) {
        int pos=tree.query(1, 0, N-1, 0, N-1).second;
        if(pos>=k-1) {
            pii curr=tree.query(1, 0, N-1, pos-k+1, pos-1);
            if(curr.first==0) pos=curr.second;
        }
        else {
            pii x = tree.query(1, 0, N-1, 0, pos-1), y=tree.query(1, 0, N-1, pos-k+1+N, N-1);
            if(y.first==0) pos=y.second;
            else if(x.first==0) pos=x.second;
        }
        a[pos]=i;
        tree.update(1, 0, N-1, pos, pos, k);
        if(pos>=k-1) tree.update(1, 0, N-1, pos-k+1, pos-1, -1);
        else {
            tree.update(1, 0,N-1, 0, pos-1, -1);
            tree.update(1, 0, N-1, pos-k+1+N, N-1, -1);
        }
    }
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6568 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6532 KB Output is correct
4 Incorrect 2 ms 6484 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 2 ms 6568 KB Output is correct
2 Correct 2 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 6 ms 6600 KB Output is correct
7 Correct 50 ms 11348 KB Output is correct
8 Correct 5 ms 6612 KB Output is correct
9 Correct 6 ms 6692 KB Output is correct
10 Correct 54 ms 11372 KB Output is correct
11 Correct 63 ms 11236 KB Output is correct
12 Correct 47 ms 11544 KB Output is correct
13 Correct 52 ms 11364 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6568 KB Output is correct
2 Correct 2 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 6 ms 6600 KB Output is correct
7 Correct 50 ms 11348 KB Output is correct
8 Correct 5 ms 6612 KB Output is correct
9 Correct 6 ms 6692 KB Output is correct
10 Correct 54 ms 11372 KB Output is correct
11 Correct 63 ms 11236 KB Output is correct
12 Correct 47 ms 11544 KB Output is correct
13 Correct 52 ms 11364 KB Output is correct
14 Correct 71 ms 12064 KB Output is correct
15 Correct 416 ms 17004 KB Output is correct
16 Correct 71 ms 12064 KB Output is correct
17 Correct 372 ms 17032 KB Output is correct
18 Correct 298 ms 16612 KB Output is correct
19 Correct 285 ms 17108 KB Output is correct
20 Correct 394 ms 16972 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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