oj.uz

Submission #1079585

# Submission time Handle Problem Language Result Execution time Memory
1079585 2024-08-28T18:03:40 Z bleahbleah Comparing Plants (IOI20_plants) C++17
30 / 100
 1224 ms 77596 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
int left[nmax][18], jumpl[nmax][18];
int 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);
   
   for(auto x : idx) {
      int mn = inserted.query_prev(x, inserted.query((x - K + 1 + N) % N, x));
      mn = (mn == -1? x : mn);
      
      jumpl[x][0] = mn <= x? x - mn : x + N - mn;
      if(jumpl[x][0] >= K) { mn = x; }
      else if(topsort[mn] <= topsort[x]) mn = x;
      
      left[x][0] = mn;
      jumpl[x][0] = mn <= x? x - mn : x + N - mn;
      
      mn = inserted.query_next(x, inserted.query(x, (x + K - 1) % N));
      mn = (mn == -1? x : mn);
      
      jumpr[x][0] = (mn >= x? mn - x : N - x + mn);
      if(jumpr[x][0] >= K) { mn = x; }
      else if(topsort[mn] <= topsort[x]) mn = x;
      
      jumpr[x][0] = (mn >= x? mn - x : N - x + mn);
      right[x][0] = mn;
      
      inserted.set(x, topsort[x]);
      //cerr << x << ": " <<  left[x][0] << ' ' << right[x][0] << '\n';
   }
   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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 73 ms 9204 KB Output is correct
7 Correct 136 ms 18876 KB Output is correct
8 Correct 792 ms 74904 KB Output is correct
9 Correct 827 ms 73960 KB Output is correct
10 Correct 824 ms 73808 KB Output is correct
11 Correct 743 ms 73992 KB Output is correct
12 Correct 689 ms 73840 KB Output is correct
13 Correct 589 ms 73916 KB Output is correct
14 Correct 748 ms 73992 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 5 ms 6700 KB Output is correct
7 Correct 70 ms 11900 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 5 ms 6744 KB Output is correct
10 Correct 65 ms 11808 KB Output is correct
11 Correct 66 ms 11784 KB Output is correct
12 Correct 90 ms 11856 KB Output is correct
13 Correct 61 ms 11860 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 5 ms 6700 KB Output is correct
7 Correct 70 ms 11900 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 5 ms 6744 KB Output is correct
10 Correct 65 ms 11808 KB Output is correct
11 Correct 66 ms 11784 KB Output is correct
12 Correct 90 ms 11856 KB Output is correct
13 Correct 61 ms 11860 KB Output is correct
14 Correct 132 ms 18944 KB Output is correct
15 Incorrect 1224 ms 73916 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 67 ms 11512 KB Output is correct
4 Correct 850 ms 75924 KB Output is correct
5 Correct 994 ms 75604 KB Output is correct
6 Correct 1070 ms 76140 KB Output is correct
7 Correct 1217 ms 75856 KB Output is correct
8 Incorrect 1130 ms 77596 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 16 ms 7496 KB Output is correct
8 Correct 11 ms 7516 KB Output is correct
9 Correct 16 ms 7516 KB Output is correct
10 Correct 13 ms 7516 KB Output is correct
11 Correct 16 ms 7504 KB Output is correct
12 Correct 15 ms 7492 KB Output is correct
13 Correct 12 ms 7560 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 3 ms 6660 KB Output is correct
6 Correct 993 ms 75416 KB Output is correct
7 Correct 1088 ms 75436 KB Output is correct
8 Correct 1050 ms 75708 KB Output is correct
9 Incorrect 1129 ms 76624 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 73 ms 9204 KB Output is correct
7 Correct 136 ms 18876 KB Output is correct
8 Correct 792 ms 74904 KB Output is correct
9 Correct 827 ms 73960 KB Output is correct
10 Correct 824 ms 73808 KB Output is correct
11 Correct 743 ms 73992 KB Output is correct
12 Correct 689 ms 73840 KB Output is correct
13 Correct 589 ms 73916 KB Output is correct
14 Correct 748 ms 73992 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 5 ms 6700 KB Output is correct
21 Correct 70 ms 11900 KB Output is correct
22 Correct 2 ms 6488 KB Output is correct
23 Correct 5 ms 6744 KB Output is correct
24 Correct 65 ms 11808 KB Output is correct
25 Correct 66 ms 11784 KB Output is correct
26 Correct 90 ms 11856 KB Output is correct
27 Correct 61 ms 11860 KB Output is correct
28 Correct 132 ms 18944 KB Output is correct
29 Incorrect 1224 ms 73916 KB Output isn't correct
30 Halted 0 ms 0 KB -