Submission #805064

#	Time	Username	Problem	Language	Result	Execution time	Memory
805064		physics07	Comparing Plants (IOI20_plants)	C++17	27 / 100	414 ms	17188 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=200002;
int a[MAX], n;
struct seg{
    pair<int, int> tree[4*MAX];
    int lazy[4*MAX];
    void init(int node, int s, int e) {
        if(s==e) {
            tree[node].second=s;
            return;
        }
        int m=s+e>>1;
        init(node*2, s, m);
        init(node*2+1, m+1, e);
        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>>1;
        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>>1;
        return min(query(node*2, s, m, l, r), query(node*2+1, m+1, e, l, r));
    }
} tree;
void init(int k, vector<int> r) {
    n=(int)r.size();
    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 idx=tree.query(1, 0, n-1, 0, n-1).second;
        if(idx>=k-1) {
            pair<int, int> curr=tree.query(1, 0, n-1, idx-k+1, idx-1);
            if(curr.first==0) idx=curr.second;
        }
        else {
            pair<int, int> x=tree.query(1, 0, n-1, 0, idx-1), y=tree.query(1, 0, n-1, idx-k+1+n, n-1);
            if(y.first==0) idx=y.second;
            else if(x.first==0) idx=x.second;
        }
        a[idx]=i;
        tree.update(1, 0, n-1, idx, idx, k);
        if(idx>=k-1) tree.update(1, 0, n-1, idx-k+1, idx-1, -1);
        else {
            tree.update(1, 0, n-1, 0, idx-1, -1);
            tree.update(1, 0, n-1, idx-k+1+n, n-1, -1);
        }
    }
}

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

Compilation message (stderr)

plants.cpp: In member function 'void seg::init(int, int, int)':
plants.cpp:15:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |         int m=s+e>>1;
      |               ~^~
plants.cpp: In member function 'void seg::update(int, int, int, int, int, int)':
plants.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int m=s+e>>1;
      |               ~^~
plants.cpp: In member function 'std::pair<int, int> seg::query(int, int, int, int, int)':
plants.cpp:45:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int m=s+e>>1;
      |               ~^~

• 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