Submission #725802

#	Time	Username	Problem	Language	Result	Execution time	Memory
725802		MohamedAliSaidane	Comparing Plants (IOI20_plants)	C++14	0 / 100	51 ms	4840 KiB

plants

#include<bits/stdc++.h>
#include "plants.h"
#include<ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpi;

#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const ll MOD = 1e9 + 7, INF = 1e18;
ll mod(ll x, ll m = MOD) {return (x + m) % m;}

const int nax = 2e5 + 4;
int n, k, sz = 1;
vi R, lazy;
vector<pii> st;
int pos[nax];

pii conq(pii a, pii b)
{
    if(a.ff == b.ff)
    {
        if(b.ss - a.ss <= k)
            return a;
        else
            return b;
    }
    return max(a, b);
}
void build(int p, int l, int r)
{
    if(l == r)
    {
        if(l < n)
            st[p] = {R[l], l};
        else
            st[p] = {-MOD, 0};
        return ;
    }
    build(2 * p, l, (l + r)/2);
    build(2 * p + 1, (l + r)/2 + 1, r);
    st[p] = conq(st[2 * p], st[2 * p + 1]);
    return ;
}
void propagate(int p, int l, int r)
{
    if(lazy[p] != 0)
    {
        if(l != r)
        {
            lazy[2 * p] += lazy[p];
            lazy[2 * p + 1] += lazy[p];
        }
        st[p].ff += lazy[p];
        lazy[p] = 0;
    }
}
void update(int p, int l, int r, int i, int j, int val)
{
    propagate(p, l, r);
    if(i > j)
        return ;
    if(l >= i && r <= j)
    {
        lazy[p] += val;
        propagate(p, l, r);
        return ;
    }
    int m = (l + r)/2;
    update(2 * p, l, m, i, min(j, m), val);
    update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
    st[p] = conq({st[2 * p].ff + lazy[2 * p], st[2 * p].ss},
                 {st[2 * p + 1].ff + lazy[2 * p + 1], st[2 * p + 1].ss});
}
pii query(int p, int l, int r, int i, int j)
{
    propagate(p, l, r);
    if(i > j)
        return {-MOD, 0};
    if(l >= i && r <= j)
        return st[p];
    int m = (l  +r)/2;
    return conq(query(2 * p, l, m, i, min(j,m)),
                query(2 * p + 1, m + 1, r, max(i, m + 1), j));
}
void init(int K, vi vec)
{
    k = K;
    R = vec;
    n = R.size();

    while(sz < n)
        sz = (sz << 1);
    st.assign(2 * sz + 1, {-MOD, MOD});
    lazy.assign(2 * sz + 1, 0);
    build(1, 0, sz - 1);
    for(int i =0; i <  n; i++)
    {
        pii u = query(1, 0, sz - 1, 0, n - 1);
       // for(int j = 0; j < n ;j ++)
          //  cout << query(1, 0, sz - 1, j, j).ff << ' ';
        //cout << '\n';
        pos[u.ss] = i;
        update(1, 0, sz - 1, u.ss, u.ss, -MOD);
        update(1, 0, sz - 1, max(0, u.ss - k + 1), u.ss - 1, 1);
        update(1, 0, sz - 1,   n - k +  u.ss + 1, n - 1, 1);
    }
}
int compare_plants(int x, int y)
{
    if(pos[x] < pos[y])
        return -1;
    else
        return 1;
}
/*
int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N, K;
    cin >> N >> K;
    vi R(N);
    for(int i =0; i < N; i++)
        cin >> R[i];
    init(K, R);
    for(int i = 0; i < N; i++)
        cout << pos[i] << ' ';
    cout << endl;
    int Q; cin >> Q;
    while(Q--)
    {
        int a, b;
        cin >> a >> b;
        cout << compare_plants(a, b) << endl;
    }
}
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25