oj.uz

Submission #1079573

# Submission time Handle Problem Language Result Execution time Memory
1079573 2024-08-28T17:43:24 Z bleahbleah Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 71064 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);
      }
   }
   
   for(int x = 0; x < sz(r); x++) {
      int mn = -1;
      jumpl[x][0] = 0;
      for(int i = (x - 1 + N) % N, d = 1; d < K; d++, i = (i - 1 + N) % N) {
         if(topsort[i] > topsort[x])
            mn = (mn == -1? i : topsort[mn] < topsort[i]? mn : i);
      }
      left[x][0] = mn == -1? x : mn;
      jumpl[x][0] = left[x][0] <= x? x - left[x][0] : x + N - left[x][0];
      
      mn = -1;
      jumpr[x][0] = 0;
      for(int i = (x + 1 + N) % N, d = 1; d < K; d++, i = (i + 1 + N) % N) {
         if(topsort[i] > topsort[x])
            mn = (mn == -1? i : topsort[mn] < topsort[i]? mn : i);
      }
      right[x][0] = mn == -1? x : mn;
      jumpr[x][0] = (right[x][0] >= x? right[x][0] - x : N - x + right[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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 61 ms 3152 KB Output is correct
7 Correct 114 ms 9812 KB Output is correct
8 Correct 577 ms 71064 KB Output is correct
9 Correct 583 ms 69972 KB Output is correct
10 Correct 577 ms 69972 KB Output is correct
11 Correct 533 ms 69968 KB Output is correct
12 Correct 525 ms 69968 KB Output is correct
13 Correct 432 ms 69976 KB Output is correct
14 Correct 596 ms 70096 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 860 KB Output is correct
7 Correct 292 ms 4868 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 11 ms 860 KB Output is correct
10 Correct 283 ms 4944 KB Output is correct
11 Correct 165 ms 4692 KB Output is correct
12 Correct 193 ms 5036 KB Output is correct
13 Correct 355 ms 4944 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 860 KB Output is correct
7 Correct 292 ms 4868 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 11 ms 860 KB Output is correct
10 Correct 283 ms 4944 KB Output is correct
11 Correct 165 ms 4692 KB Output is correct
12 Correct 193 ms 5036 KB Output is correct
13 Correct 355 ms 4944 KB Output is correct
14 Correct 2653 ms 9896 KB Output is correct
15 Execution timed out 4048 ms 14272 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 65 ms 3752 KB Output is correct
4 Correct 624 ms 69968 KB Output is correct
5 Correct 854 ms 70104 KB Output is correct
6 Correct 2729 ms 69896 KB Output is correct
7 Execution timed out 4094 ms 22352 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 15 ms 1136 KB Output is correct
8 Correct 11 ms 1116 KB Output is correct
9 Correct 15 ms 1116 KB Output is correct
10 Correct 12 ms 1116 KB Output is correct
11 Correct 14 ms 1116 KB Output is correct
12 Correct 14 ms 1172 KB Output is correct
13 Correct 14 ms 980 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 847 ms 70144 KB Output is correct
7 Correct 2718 ms 69968 KB Output is correct
8 Execution timed out 4054 ms 21476 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 61 ms 3152 KB Output is correct
7 Correct 114 ms 9812 KB Output is correct
8 Correct 577 ms 71064 KB Output is correct
9 Correct 583 ms 69972 KB Output is correct
10 Correct 577 ms 69972 KB Output is correct
11 Correct 533 ms 69968 KB Output is correct
12 Correct 525 ms 69968 KB Output is correct
13 Correct 432 ms 69976 KB Output is correct
14 Correct 596 ms 70096 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 11 ms 860 KB Output is correct
21 Correct 292 ms 4868 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 11 ms 860 KB Output is correct
24 Correct 283 ms 4944 KB Output is correct
25 Correct 165 ms 4692 KB Output is correct
26 Correct 193 ms 5036 KB Output is correct
27 Correct 355 ms 4944 KB Output is correct
28 Correct 2653 ms 9896 KB Output is correct
29 Execution timed out 4048 ms 14272 KB Time limit exceeded
30 Halted 0 ms 0 KB -