oj.uz

Submission #1079595

# Submission time Handle Problem Language Result Execution time Memory
1079595 2024-08-28T18:23:26 Z bleahbleah Comparing Plants (IOI20_plants) C++17
30 / 100
 1341 ms 79596 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);
   
   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 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 60 ms 9196 KB Output is correct
7 Correct 115 ms 18772 KB Output is correct
8 Correct 549 ms 75016 KB Output is correct
9 Correct 557 ms 74072 KB Output is correct
10 Correct 568 ms 73952 KB Output is correct
11 Correct 551 ms 73812 KB Output is correct
12 Correct 522 ms 73916 KB Output is correct
13 Correct 405 ms 73808 KB Output is correct
14 Correct 663 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 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 4 ms 6744 KB Output is correct
7 Correct 60 ms 12040 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 59 ms 12040 KB Output is correct
11 Correct 60 ms 11856 KB Output is correct
12 Correct 87 ms 12016 KB Output is correct
13 Correct 80 ms 12112 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 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 4 ms 6744 KB Output is correct
7 Correct 60 ms 12040 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 59 ms 12040 KB Output is correct
11 Correct 60 ms 11856 KB Output is correct
12 Correct 87 ms 12016 KB Output is correct
13 Correct 80 ms 12112 KB Output is correct
14 Correct 154 ms 14360 KB Output is correct
15 Incorrect 1341 ms 79596 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 82 ms 11540 KB Output is correct
4 Correct 670 ms 73920 KB Output is correct
5 Correct 773 ms 73916 KB Output is correct
6 Correct 865 ms 73920 KB Output is correct
7 Correct 1045 ms 74480 KB Output is correct
8 Incorrect 1234 ms 78016 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 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 17 ms 7176 KB Output is correct
8 Correct 13 ms 7248 KB Output is correct
9 Correct 16 ms 7180 KB Output is correct
10 Correct 13 ms 7260 KB Output is correct
11 Correct 19 ms 7180 KB Output is correct
12 Correct 17 ms 7128 KB Output is correct
13 Correct 13 ms 7128 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6500 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 740 ms 74220 KB Output is correct
7 Correct 860 ms 74072 KB Output is correct
8 Correct 897 ms 74320 KB Output is correct
9 Incorrect 1282 ms 78088 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 60 ms 9196 KB Output is correct
7 Correct 115 ms 18772 KB Output is correct
8 Correct 549 ms 75016 KB Output is correct
9 Correct 557 ms 74072 KB Output is correct
10 Correct 568 ms 73952 KB Output is correct
11 Correct 551 ms 73812 KB Output is correct
12 Correct 522 ms 73916 KB Output is correct
13 Correct 405 ms 73808 KB Output is correct
14 Correct 663 ms 73992 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 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 4 ms 6744 KB Output is correct
21 Correct 60 ms 12040 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 4 ms 6748 KB Output is correct
24 Correct 59 ms 12040 KB Output is correct
25 Correct 60 ms 11856 KB Output is correct
26 Correct 87 ms 12016 KB Output is correct
27 Correct 80 ms 12112 KB Output is correct
28 Correct 154 ms 14360 KB Output is correct
29 Incorrect 1341 ms 79596 KB Output isn't correct
30 Halted 0 ms 0 KB -