Submission #301408

#	Time	Username	Problem	Language	Result	Execution time	Memory
301408		egorlifar	Comparing Plants (IOI20_plants)	C++17	44 / 100	2781 ms	47852 KiB

plants

#include "plants.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int MAXN = 200228;


int n, k;


vector<pair<int, int> > getCircleSegment(int l, int r) {
	l += 3 * n;
	r += 3 * n;
    l %= n;
    r %= n;
    if (l <= r) {
        return vector<pair<int, int> >{{l, r}};
    }
    return vector<pair<int, int> >{{l, n - 1}, {0, r}};
}



struct rmq
{
    vector<pair<pair<ll, ll>, int> > d;
    vector<pair<ll, ll> > mod;
    int ss = 1;
    void init(int n) {
        while (ss < n) {
            ss <<= 1;
        }
        d.resize(2 * ss, mp(mp(0LL, 0LL), 0));
        mod.resize(2 * ss, mp(0LL, 0LL));
    }
    void push(int v) {
        if (mod[v].first != 0 || mod[v].second != 0) {
            d[v].first.first += mod[v].first;
            d[v].first.second += mod[v].second;
            if (v < ss) {
                mod[v * 2].first += mod[v].first;
                mod[v * 2].second += mod[v].second;
                mod[v * 2 + 1].first += mod[v].first;
                mod[v * 2 + 1].second += mod[v].second;
            }
            mod[v].first = 0;
            mod[v].second = 0;
        }
    }
    void add(int v, int vl, int vr, int l, int r, ll x, ll y) {
        if (vl > r || vr < l) {
            push(v);
            return;
        }
        if (l <= vl && vr <= r) {
            mod[v].first += x;
            mod[v].second += y;
            push(v);
            return;
        }
        push(v);
        add(v * 2, vl, (vl + vr) / 2, l, r, x, y);
        add(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x, y);
        d[v] = min(d[v * 2], d[v * 2 + 1]);
    }
} kek, kek1;


//r[i] = 0
//sum от r[i] = 0 тоже 0
int h[MAXN];
int order[MAXN];


void add(int i) {
    auto kr = getCircleSegment(i + 1, i + k);
    for (auto y: kr) {
        kek.add(1, 1, kek.ss, y.first + 1, y.second + 1, 0, 1);
        kek1.add(1, 1, kek.ss, y.first + 1, y.second + 1, 0, 1);
    }
}



void del(int i) {
    auto kr = getCircleSegment(i + 1, i + k);
    for (auto y: kr) {
    	//cout << y.first << ' ' << y.second << endl; 
        kek.add(1, 1, kek.ss, y.first + 1, y.second + 1, 0, -1);
        kek1.add(1, 1, kek.ss, y.first + 1, y.second + 1, 0, -1);
    }
    auto kr1 = getCircleSegment(i - k + n, i - 1 + n);
    for (auto y: kr1) {
        kek.add(1, 1, kek.ss, y.first + 1, y.second + 1, -1, 0);
        kek1.add(1, 1, kek.ss, y.first + 1, y.second + 1, -1, 0);
    }
}


void push() {
	while (true) {
	    kek1.push(1);
	    auto x = kek1.d[1];
	    if (x.first.first != 0) {
	    	return;
	    }
	 //  cout << x.first.first << ' ' << x.first.second << endl;
	    int i = x.second;
	    kek1.add(1, 1, kek1.ss, i + 1, i + 1, 1e9, 0);
	    add(i);
	}
}


void init(int _k, vector<int> r) {
    k = _k;
    k--;
    n = sz(r);
    vector<int> bads;
    for (int i = 0; i < n; i++) {
        h[i] = r[i];
        if (r[i] == 0) {
            bads.pb(i);
        }
    }
    kek.init(n);
    kek1.init(n);
    for (int i = 0; i < n; i++) {
        kek.d[kek.ss + i].first.first = r[i];
        kek.d[kek.ss + i].second = i;
        if (r[i]) {
            kek1.d[kek.ss + i].first.first = r[i];
            kek1.d[kek.ss + i].second = i;
        } else {
            kek1.d[kek1.ss + i].first.first = 1e9;
            kek1.d[kek1.ss + i].second = i;
        }
    }
    for (int i = n; i < kek.ss; i++) {
        kek.d[kek.ss + i].first.first = 1e9;
        kek.d[kek.ss + i].second = i;
        kek1.d[kek1.ss + i].first.first = 1e9;
        kek1.d[kek1.ss + i].second = i;
    }
    for (int i = kek.ss - 1; i >= 1; i--) {
    	kek.d[i] = min(kek.d[i * 2], kek.d[i * 2 + 1]);
    	kek1.d[i] = min(kek1.d[i * 2], kek1.d[i * 2 + 1]);
    }
    for (auto x: bads) {
        add(x);
    }
    for (int it = 0; it < n; it++) {
        kek.push(1);
        auto f = kek.d[1];
     //   cout << f.first.first << ' ' << f.first.second << endl;
        assert(f.first.first == 0 && f.first.second == 0);
        int i = f.second;
        order[i] = it;
        del(i);
        kek.add(1, 1, kek.ss, i + 1, i + 1, 1e9, 0);
        push();
    }
}   

int compare_plants(int x, int y) {
    if (order[x] == order[y]) {
        return 0;
    }
    return (order[x] < order[y] ? 1: -1);
}

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