oj.uz

Submission #301408

# Submission time Handle Problem Language Result Execution time Memory
301408 2020-09-17T22:39:21 Z egorlifar Comparing Plants (IOI20_plants) C++17
44 / 100
 2781 ms 47852 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 109 ms 4600 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 107 ms 4600 KB Output is correct
11 Correct 98 ms 4476 KB Output is correct
12 Correct 98 ms 4756 KB Output is correct
13 Correct 104 ms 4544 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 109 ms 4600 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 107 ms 4600 KB Output is correct
11 Correct 98 ms 4476 KB Output is correct
12 Correct 98 ms 4756 KB Output is correct
13 Correct 104 ms 4544 KB Output is correct
14 Correct 244 ms 8728 KB Output is correct
15 Correct 2730 ms 46972 KB Output is correct
16 Correct 247 ms 8828 KB Output is correct
17 Correct 2781 ms 46968 KB Output is correct
18 Correct 1441 ms 47344 KB Output is correct
19 Correct 1473 ms 47276 KB Output is correct
20 Correct 2156 ms 46968 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 78 ms 3576 KB Output is correct
4 Correct 908 ms 47412 KB Output is correct
5 Correct 1224 ms 47096 KB Output is correct
6 Correct 1800 ms 46968 KB Output is correct
7 Correct 2344 ms 46968 KB Output is correct
8 Correct 2671 ms 46968 KB Output is correct
9 Correct 1031 ms 47224 KB Output is correct
10 Correct 1066 ms 46968 KB Output is correct
11 Correct 677 ms 47852 KB Output is correct
12 Correct 961 ms 47096 KB Output is correct
13 Correct 1375 ms 47596 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -