oj.uz

Submission #1079572

# Submission time Handle Problem Language Result Execution time Memory
1079572 2024-08-28T17:39:36 Z bleahbleah Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 69756 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) {
      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);
   }
};

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) {
      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();
   
   vector<int> erased(N, 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) {
         for(int i = (x - 1 + N) % N, d = 1; d < K; d++, i = (i - 1 + N) % N) {
            if(erased[i]) continue;
            r[i]--;
            if(r[i] == 0) erased[i] = 1, Queue::insert(i);
         }
      }
   }
   
   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 0 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 61 ms 3060 KB Output is correct
7 Correct 103 ms 9552 KB Output is correct
8 Correct 438 ms 68004 KB Output is correct
9 Correct 464 ms 67152 KB Output is correct
10 Correct 442 ms 66896 KB Output is correct
11 Correct 472 ms 66900 KB Output is correct
12 Correct 433 ms 66780 KB Output is correct
13 Correct 347 ms 66896 KB Output is correct
14 Correct 482 ms 66900 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 0 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 14 ms 892 KB Output is correct
7 Correct 369 ms 6316 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 14 ms 772 KB Output is correct
10 Correct 355 ms 6564 KB Output is correct
11 Correct 217 ms 6480 KB Output is correct
12 Correct 240 ms 6568 KB Output is correct
13 Correct 455 ms 6644 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 0 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 14 ms 892 KB Output is correct
7 Correct 369 ms 6316 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 14 ms 772 KB Output is correct
10 Correct 355 ms 6564 KB Output is correct
11 Correct 217 ms 6480 KB Output is correct
12 Correct 240 ms 6568 KB Output is correct
13 Correct 455 ms 6644 KB Output is correct
14 Correct 3521 ms 11608 KB Output is correct
15 Execution timed out 4058 ms 14196 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 69 ms 5264 KB Output is correct
4 Correct 592 ms 69460 KB Output is correct
5 Correct 854 ms 69756 KB Output is correct
6 Correct 3658 ms 69680 KB Output is correct
7 Execution timed out 4017 ms 13904 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 15 ms 1456 KB Output is correct
8 Correct 12 ms 1372 KB Output is correct
9 Correct 14 ms 1372 KB Output is correct
10 Correct 12 ms 1372 KB Output is correct
11 Correct 15 ms 1372 KB Output is correct
12 Correct 16 ms 1368 KB Output is correct
13 Correct 12 ms 1372 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 829 ms 69000 KB Output is correct
7 Correct 3794 ms 69048 KB Output is correct
8 Execution timed out 4035 ms 13136 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 61 ms 3060 KB Output is correct
7 Correct 103 ms 9552 KB Output is correct
8 Correct 438 ms 68004 KB Output is correct
9 Correct 464 ms 67152 KB Output is correct
10 Correct 442 ms 66896 KB Output is correct
11 Correct 472 ms 66900 KB Output is correct
12 Correct 433 ms 66780 KB Output is correct
13 Correct 347 ms 66896 KB Output is correct
14 Correct 482 ms 66900 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 14 ms 892 KB Output is correct
21 Correct 369 ms 6316 KB Output is correct
22 Correct 3 ms 604 KB Output is correct
23 Correct 14 ms 772 KB Output is correct
24 Correct 355 ms 6564 KB Output is correct
25 Correct 217 ms 6480 KB Output is correct
26 Correct 240 ms 6568 KB Output is correct
27 Correct 455 ms 6644 KB Output is correct
28 Correct 3521 ms 11608 KB Output is correct
29 Execution timed out 4058 ms 14196 KB Time limit exceeded
30 Halted 0 ms 0 KB -