Submission #814839

#	Time	Username	Problem	Language	Result	Execution time	Memory
814839		vjudge1	Comparing Plants (IOI20_plants)	C++17	27 / 100	416 ms	17108 KiB

plants

#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
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25