oj.uz

Submission #1079598

# Submission time Handle Problem Language Result Execution time Memory
1079598 2024-08-28T18:25:49 Z bleahbleah Comparing Plants (IOI20_plants) C++17
100 / 100
 1284 ms 139604 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
 
using namespace std;
 
using ll = long long;
#define sz(x) ((int)(x).size())
 
int K, N;
const int nmax = 2e5 + 5;
 
template<typename T>
struct AINT {
   vector<T> aint;
   int n;
   void init(int n_) {
      n = n_;
      aint.assign(2 * n + 5, T());
   }
   template<int dir = 0, class CB> void walk(CB&& cb) { walk<dir>(cb, 0, n - 1); }
   template<int dir = 0, class CB> void walk(CB&& cb, int l, int r) { walk<dir>(cb, l, r, 1, 0, n - 1); }
   template<int dir = 0, class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) {  
      if(cr < l || r < cl) return;
      if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
      int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
      aint[node].push(aint[L], aint[R]);
      if(dir == 0) { walk<dir>(cb, l, r, L, cl, mid); walk<dir>(cb, l, r, R, mid + 1, cr); }
      if(dir == 1) { walk<dir>(cb, l, r, R, mid + 1, cr); walk<dir>(cb, l, r, L, cl, mid); }
      aint[node].pull(aint[L], aint[R]);
   }
};
 
struct MinFindUnit {
   int mn;
   int lazy = 0;
   void push(MinFindUnit& L, MinFindUnit& R) {
      if(lazy == 0) return;
      L.lazy += lazy;
      R.lazy += lazy;
      R.mn += lazy;
      L.mn += lazy;
      lazy = 0;
      return;
   }
   void pull(MinFindUnit& L, MinFindUnit& R) {
      mn = min(L.mn, R.mn);
      return;
   }
};
 
struct MinFind : AINT<MinFindUnit> {
   int query_next(int t, int limit) {
      if(aint[1].mn > limit) return -1;
      for(int itt = 0; itt < 2; itt++) {
         walk([&](auto& a, int cl, int cr) {
            if(t < cl) return 0;
            if(cr < t) return 0;
            if(a.mn > limit) {
               t = cr + 1;
               return 0;
            }
            if(cl == cr) { return 0; }
            return 1;
         }, t, n - 1);
         if(t == n) t = 0;
      }
      return t;
   }
   
   
   int query_prev(int t, int limit) {
      if(aint[1].mn > limit) return -1;
      for(int itt = 0; itt < 2; itt++) {
         walk<1>([&](auto& a, int cl, int cr) {
            if(t < cl) return 0;
            if(cr < t) return 0;
            if(a.mn > limit) {
               t = cl - 1;
               return 0;
            }
            if(cl == cr) { return 0; }
            return 1;
         }, 0, t);
         if(t == -1) t = n - 1;
      }
      return t;
   }
   
   void add(int l, int r, int x) {
      if(l > r) { add(l, N - 1, x), add(0, r, x); return; }
      walk([&](auto& a, int cl, int cr) {
         a.mn += x;
         a.lazy += x;
         return 0;
      }, l, r);
   }
   void set(int p, int x) {
      set(p, p, x);
   }
   void set(int l, int r, int x) {
      walk([&](auto& a, int cl, int cr) {
         if(cl != cr) return 1;
         a.mn = x;
         a.lazy = 0;
         return 0;
      }, l, r);
   }
   int query(int l, int r, int x = 1e9 + 6) {
      if(l > r) return min(query(l, N - 1), query(0, r));
      walk([&](auto& a, int cl, int cr) {
         x = min(x, a.mn);
         return 0;
      }, l, r);
      return x;
   }
};
 
MinFind nextinqueue;
namespace Queue {
   int next[nmax];
   MinFind inside;
   
   
   auto rdist = [](int x, int d) {
      return d < x? N - x + d : d - x;
   };
   auto ldist = [](int x, int d) {
      return d <= x? x - d : x + N - d;
   };
   
   set<int> heads;
   void init() {
      inside.init(N);
      inside.set(0, N - 1, 1);
   }
   void insert(int node) {
      nextinqueue.set(node, 1e9 + 5);
      heads.emplace(node);
      inside.set(node, 0);
      next[node] = -1;
      
      int nx = inside.query_next((node + 1) % N, 0);
      int pr = inside.query_prev((node - 1 + N) % N, 0);
      
      if(nx != node && rdist(node, nx) < K) {
         next[node] = nx;
         if(heads.count(nx)) heads.erase(nx);
      }
      if(pr != node && ldist(node, pr) < K) {
         heads.erase(node);
         next[pr] = node;
      }
   }
   
   vector<int> prune() {
      vector<int> rez;
      for(auto x : heads)
         rez.emplace_back(x), inside.set(x, 1);
      heads.clear();
      for(auto x : rez)
         if(next[x] != -1) heads.emplace(next[x]);
      return rez;
   }
}
 
vector<int> topsort;
#define left ofia
#define right goa
ll left[nmax][18], jumpl[nmax][18];
ll right[nmax][18], jumpr[nmax][18];
 
void init(int k__, std::vector<int> r) {
   auto T = r;
   K = k__;
   N = sz(r);
   topsort.resize(N);
   Queue::init();
   nextinqueue.init(N);
   
   vector<int> erased(N, 0);
   
   nextinqueue.walk([&](auto& a, int cl, int cr) {
      if(cl != cr) return 1;
      a.mn = r[cl];
      return 0;
   });
   
   for(int i = 0; i < sz(r); i++) 
      if(r[i] == 0) erased[i] = 1, Queue::insert(i);
   
   
   int color = 0;
   while(sz(Queue::heads)) {
      auto rem = Queue::prune();
      ++color;
      for(auto x : rem) topsort[x] = color;
      
      for(auto x : rem)
         nextinqueue.add((x - K + 1 + N) % N, x, -1);
      while(1) {
         int x = nextinqueue.query_next(0, 0);
         if(x == -1) break;
         Queue::insert(x);
      }
   }
   
   vector<int> idx(N);
   iota(all(idx), 0);
   sort(all(idx), [&](int a, int b) { return topsort[a] > topsort[b]; });
   
   MinFind inserted;
   inserted.init(N);
   inserted.set(0, N - 1, 1e9 + 5);
   
   auto cmp = [&](int a, int b) { return make_pair(topsort[a], a) < make_pair(topsort[b], b); };
   set<int, decltype(cmp)> heap(cmp);
   for(int i = 0; i < K; i++) heap.insert(i);
   for(int i = 0, r = K; i < N; i++, r = (r + 1) % N) {
      auto it = heap.upper_bound(i);
      if(it == heap.end()) right[i][0] = i;
      else right[i][0] = *it;
      heap.erase(i);
      heap.insert(r);
   } 
   heap.clear();
   for(int i = 0; i < K - 1; i++) heap.insert(i);
   for(int l = 0, i = K - 1; l < N; i = (i + 1) % N, l++) {
      heap.insert(i);
      auto it = heap.upper_bound(i);
      if(it == heap.end()) left[i][0] = i;
      else left[i][0] = *it;
      heap.erase(l);
   }
   
   for(int i = 0; i < N; i++) {
      jumpr[i][0] = Queue::rdist(i, right[i][0]);
      jumpl[i][0] = Queue::ldist(i, left[i][0]);
   }
   
   for(int step = 1; step < 18; step++)
      for(int i = 0; i < N; i++)
         left[i][step] = left[left[i][step - 1]][step - 1], jumpl[i][step] = jumpl[i][step - 1] + jumpl[left[i][step - 1]][step - 1],
         right[i][step] = right[right[i][step - 1]][step - 1], jumpr[i][step] = jumpr[i][step - 1] + jumpr[right[i][step - 1]][step - 1];
      
   
	return;
}
 
bool compare_smaller(int x, int y) {
   auto rdist = [&](int d) {
      return d < x? N - x + d : d - x;
   };
   auto ldist = [&](int d) {
      return d <= x? x - d : x + N - d;
   };
   
   int st = x, buffer = rdist(y);
   for(int i = 17; i >= 0; i--) {
      if(buffer < jumpr[st][i]) continue;
      buffer -= jumpr[st][i];
      st = right[st][i];
   }
   if(st == y) return 1;
   if(rdist(y) - rdist(st) < K && topsort[y] > topsort[st]) return 1;
   
   st = x;
   buffer = ldist(y);
   for(int i = 17; i >= 0; i--) {
      if(buffer < jumpl[st][i]) continue;
      buffer -= jumpl[st][i];
      st = left[st][i];
   }
   
   if(st == y) return 1;
   if(ldist(y) - ldist(st) < K && topsort[y] > topsort[st]) return 1;
   return 0;
}
 
 
int compare_plants(int x, int y) {
   return compare_smaller(x, y)? 1 : compare_smaller(y, x)? -1 : 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 65 ms 11236 KB Output is correct
7 Correct 118 ms 21252 KB Output is correct
8 Correct 651 ms 131256 KB Output is correct
9 Correct 672 ms 130504 KB Output is correct
10 Correct 673 ms 130388 KB Output is correct
11 Correct 639 ms 130316 KB Output is correct
12 Correct 647 ms 130224 KB Output is correct
13 Correct 527 ms 130544 KB Output is correct
14 Correct 771 ms 130384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 61 ms 14600 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 7 ms 10844 KB Output is correct
10 Correct 63 ms 14600 KB Output is correct
11 Correct 69 ms 14484 KB Output is correct
12 Correct 94 ms 14576 KB Output is correct
13 Correct 59 ms 14676 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct
6 Correct 5 ms 10844 KB Output is correct
7 Correct 61 ms 14600 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 7 ms 10844 KB Output is correct
10 Correct 63 ms 14600 KB Output is correct
11 Correct 69 ms 14484 KB Output is correct
12 Correct 94 ms 14576 KB Output is correct
13 Correct 59 ms 14676 KB Output is correct
14 Correct 131 ms 22808 KB Output is correct
15 Correct 1246 ms 136020 KB Output is correct
16 Correct 124 ms 21696 KB Output is correct
17 Correct 1284 ms 136116 KB Output is correct
18 Correct 748 ms 135248 KB Output is correct
19 Correct 891 ms 134992 KB Output is correct
20 Correct 1273 ms 139604 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 72 ms 13580 KB Output is correct
4 Correct 728 ms 130384 KB Output is correct
5 Correct 852 ms 130384 KB Output is correct
6 Correct 904 ms 130312 KB Output is correct
7 Correct 1018 ms 130992 KB Output is correct
8 Correct 1194 ms 134740 KB Output is correct
9 Correct 666 ms 133256 KB Output is correct
10 Correct 717 ms 133412 KB Output is correct
11 Correct 521 ms 133204 KB Output is correct
12 Correct 815 ms 133460 KB Output is correct
13 Correct 682 ms 136188 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8636 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 16 ms 9316 KB Output is correct
8 Correct 12 ms 9308 KB Output is correct
9 Correct 15 ms 9308 KB Output is correct
10 Correct 12 ms 9308 KB Output is correct
11 Correct 15 ms 9308 KB Output is correct
12 Correct 15 ms 9248 KB Output is correct
13 Correct 12 ms 9276 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 801 ms 130308 KB Output is correct
7 Correct 881 ms 130272 KB Output is correct
8 Correct 879 ms 130736 KB Output is correct
9 Correct 1184 ms 134576 KB Output is correct
10 Correct 667 ms 132432 KB Output is correct
11 Correct 823 ms 137044 KB Output is correct
12 Correct 627 ms 132180 KB Output is correct
13 Correct 792 ms 132432 KB Output is correct
14 Correct 787 ms 132692 KB Output is correct
15 Correct 925 ms 133456 KB Output is correct
16 Correct 652 ms 132480 KB Output is correct
17 Correct 747 ms 132688 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 65 ms 11236 KB Output is correct
7 Correct 118 ms 21252 KB Output is correct
8 Correct 651 ms 131256 KB Output is correct
9 Correct 672 ms 130504 KB Output is correct
10 Correct 673 ms 130388 KB Output is correct
11 Correct 639 ms 130316 KB Output is correct
12 Correct 647 ms 130224 KB Output is correct
13 Correct 527 ms 130544 KB Output is correct
14 Correct 771 ms 130384 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8536 KB Output is correct
19 Correct 1 ms 8536 KB Output is correct
20 Correct 5 ms 10844 KB Output is correct
21 Correct 61 ms 14600 KB Output is correct
22 Correct 3 ms 8540 KB Output is correct
23 Correct 7 ms 10844 KB Output is correct
24 Correct 63 ms 14600 KB Output is correct
25 Correct 69 ms 14484 KB Output is correct
26 Correct 94 ms 14576 KB Output is correct
27 Correct 59 ms 14676 KB Output is correct
28 Correct 131 ms 22808 KB Output is correct
29 Correct 1246 ms 136020 KB Output is correct
30 Correct 124 ms 21696 KB Output is correct
31 Correct 1284 ms 136116 KB Output is correct
32 Correct 748 ms 135248 KB Output is correct
33 Correct 891 ms 134992 KB Output is correct
34 Correct 1273 ms 139604 KB Output is correct
35 Correct 1 ms 8536 KB Output is correct
36 Correct 1 ms 8536 KB Output is correct
37 Correct 72 ms 13580 KB Output is correct
38 Correct 728 ms 130384 KB Output is correct
39 Correct 852 ms 130384 KB Output is correct
40 Correct 904 ms 130312 KB Output is correct
41 Correct 1018 ms 130992 KB Output is correct
42 Correct 1194 ms 134740 KB Output is correct
43 Correct 666 ms 133256 KB Output is correct
44 Correct 717 ms 133412 KB Output is correct
45 Correct 521 ms 133204 KB Output is correct
46 Correct 815 ms 133460 KB Output is correct
47 Correct 682 ms 136188 KB Output is correct
48 Correct 1 ms 8536 KB Output is correct
49 Correct 1 ms 8536 KB Output is correct
50 Correct 1 ms 8540 KB Output is correct
51 Correct 1 ms 8636 KB Output is correct
52 Correct 2 ms 8536 KB Output is correct
53 Correct 2 ms 8540 KB Output is correct
54 Correct 16 ms 9316 KB Output is correct
55 Correct 12 ms 9308 KB Output is correct
56 Correct 15 ms 9308 KB Output is correct
57 Correct 12 ms 9308 KB Output is correct
58 Correct 15 ms 9308 KB Output is correct
59 Correct 15 ms 9248 KB Output is correct
60 Correct 12 ms 9276 KB Output is correct
61 Correct 77 ms 15444 KB Output is correct
62 Correct 136 ms 25144 KB Output is correct
63 Correct 757 ms 133736 KB Output is correct
64 Correct 839 ms 133460 KB Output is correct
65 Correct 941 ms 133768 KB Output is correct
66 Correct 951 ms 134224 KB Output is correct
67 Correct 1168 ms 138256 KB Output is correct
68 Correct 738 ms 133256 KB Output is correct
69 Correct 1004 ms 137552 KB Output is correct
70 Correct 760 ms 133200 KB Output is correct
71 Correct 865 ms 133368 KB Output is correct
72 Correct 915 ms 133712 KB Output is correct
73 Correct 999 ms 134220 KB Output is correct
74 Correct 776 ms 133484 KB Output is correct
75 Correct 761 ms 133456 KB Output is correct