Submission #420456

#TimeUsernameProblemLanguageResultExecution timeMemory
420456idk321Comparing Plants (IOI20_plants)C++14
5 / 100
96 ms9448 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; int k; vector<int> r; vector<int> prefR; const int N = 200005; int tree[4 * N]; int treeInd[4 * N]; int lazy[4 * N]; const int M = 1000000000; int n; int getSum(int from, int to) { int res = prefR[to + 1]; res -= prefR[from]; return res; } void push(int node) { for (int i = 0; i <= 1; i++) { tree[node * 2 +i] += lazy[node]; lazy[node * 2 + i] += lazy[node]; } lazy[node] = 0; } void add(int num, int from, int to, int a, int b, int node) { if (from <= a && b <= to) { if (a == b) treeInd[node] = a; tree[node] += num; lazy[node] += num; return; } push(node); int mid = (a + b) / 2; if (from <= mid) add(num, from, to, a, mid, node * 2); if (to > mid) add(num, from, to, mid + 1, b, node * 2+ 1); if (tree[node * 2] <= tree[node * 2 +1]) { treeInd[node] = treeInd[node * 2]; tree[node] = tree[node * 2]; } else { treeInd[node] = treeInd[node * 2 + 1]; tree[node] = tree[node * 2 + 1]; } } array<int, 2> minIndOn(int from, int to, int a, int b, int node) { if (from <= a && b <= to) { return {tree[node], treeInd[node]}; } push(node); int mid = (a + b) / 2; array<int, 2> res = {M, -1}; if (from <= mid) res = min(res, minIndOn(from, to, a, mid, node *2)); if (to > mid) res = min(res, minIndOn(from, to, mid + 1, b, node * 2 + 1)); return res; } vector<int> order; void init(int K, std::vector<int> R) { k = K; r = R; n = r.size(); prefR.resize(r.size() + 1); for (int i = 1; i <= r.size(); i++) { prefR[i] = r[i - 1]; prefR[i] += prefR[i - 1]; } order.resize(n); if (2 * k > n) { for (int i = 0; i < n; i++) { add(r[i], i, i, 0, n - 1, 1); } for (int t = 0; t < n; t++) { array<int, 2> res = {-1, -1}; auto res1 = minIndOn(0, n - 1, 0, n - 1, 1); if (res1[1] != n - 1) { auto res2 = minIndOn(res1[1] + 1, n - 1, 0, n - 1, 1); if (res2[0] == 0) { int dist = res2[1] - res1[1]; if (dist < k) { res = res1; } else { res = res2; } } else { res = res1; } } else res = res1; order[res[1]] = t; add(M, res[1], res[1], 0, n - 1, 1); if (res[1] != 0) add(-1, max(0, res[1] - k + 1), res[1] - 1, 0, n - 1, 1); int still = k - (res[1] - max(0, res[1] - k + 1) + 1); if (still > 0) { add(-1, n - still, n - 1, 0, n - 1, 1); } } } return; } int compare_plants(int x, int y) { if (k == 2) { if (getSum(x, y - 1) == (y - x)) return -1; if (getSum(x, y - 1) == 0) return 1; int sum1 = getSum(y, n -1); if (x != 0) sum1 += getSum(0, x - 1); if (sum1 == (n - y) + x) return 1; if (sum1 == 0) return -1; return 0; } if (order[x] < order[y]) { return 1; } if (order[x] > order[y]) return -1; return 0; } //3 2 1 4 0 /* 5 3 1 0 1 1 0 2 0 1 */

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 1; i <= r.size(); i++)
      |                     ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...