oj.uz

Submission #815494

# Submission time Handle Problem Language Result Execution time Memory
815494 2023-08-08T15:51:32 Z MODDI Comparing Plants (IOI20_plants) C++14
0 / 100
 4000 ms 6484 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++) {
        auto [pos, p]=tree.query(1, 0, N-1, 0, N-1);
        while(pos == 0){
			 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;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [pos, p]=tree.query(1, 0, N-1, 0, N-1);
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4065 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4070 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 6484 KB Time limit exceeded
2 Halted 0 ms 0 KB -