oj.uz

Submission #1079580

# Submission time Handle Problem Language Result Execution time Memory
1079580 2024-08-28T17:55:19 Z bleahbleah Comparing Plants (IOI20_plants) C++17
5 / 100
 1203 ms 77192 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) {
      walk([&](auto& a, int cl, int cr) {
         if(cl != cr) return 1;
         a.mn = x;
         a.lazy = 0;
         return 0;
      }, p, p);
   }
   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);
   }
};

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, 1);
   
   for(auto x : topsort) cerr << x << ' ';
   cerr << '\n';
   
   for(auto x : idx) {
      int mn = inserted.query_prev(x, 0);
      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, 0);
      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, 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 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 69 ms 10168 KB Output is correct
7 Correct 173 ms 20244 KB Output is correct
8 Correct 1155 ms 77192 KB Output is correct
9 Correct 1203 ms 76368 KB Output is correct
10 Correct 1149 ms 76568 KB Output is correct
11 Correct 1118 ms 76704 KB Output is correct
12 Correct 1155 ms 76956 KB Output is correct
13 Correct 978 ms 77080 KB Output is correct
14 Correct 1167 ms 77076 KB Output is correct

Subtask #2
0 / 14.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 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.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 Incorrect 1 ms 6492 KB Output isn't correct
5 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 69 ms 10168 KB Output is correct
7 Correct 173 ms 20244 KB Output is correct
8 Correct 1155 ms 77192 KB Output is correct
9 Correct 1203 ms 76368 KB Output is correct
10 Correct 1149 ms 76568 KB Output is correct
11 Correct 1118 ms 76704 KB Output is correct
12 Correct 1155 ms 76956 KB Output is correct
13 Correct 978 ms 77080 KB Output is correct
14 Correct 1167 ms 77076 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Incorrect 1 ms 6492 KB Output isn't correct
18 Halted 0 ms 0 KB -