oj.uz

Submission #996921

# Submission time Handle Problem Language Result Execution time Memory
996921 2024-06-11T12:27:53 Z cadmiumsky Sweeping (JOI20_sweeping) C++17
100 / 100
 6025 ms 687008 KB 
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
 
using ll = long long;
using ld = long double;
 
//#define int ll
#define sz(x) ((int)(x).size())
 
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
 
#ifndef DLOCAL
   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#else
   mt19937 rng(69420);
#endif
 
template<typename T>
struct Treap { // neironic de 2 ani nu am mai bagat treap. Gen, doi ani, se implinesc 3 in 3 luni. E jale
   struct Node {
      T data;
      Node *l, *r;
      int pri;
   } *nil = new Node{T(), 0, 0, 0};
   using ns = Node*;
   struct pns { ns l; ns r; };
   
   ns updnode(ns node, ns x, int side) {
      (side? node -> r : node -> l) = x;
      node -> data.pull(node -> l -> data, node -> r -> data);
      return node;
   }
   
   void push(ns node) {
      if(node == nil) return;
      node -> data.push(node -> l -> data, node -> r -> data);
      return;
   }
   
   ns merge(ns l, ns r) {
      push(l), push(r);
      return l == nil? r :
               r == nil? l :
                  l -> pri > r -> pri? updnode(l, merge(l -> r, r), 1):
                     updnode(r, merge(l, r -> l), 0);
   }
   
   template<class CB> pns split(CB&& cb, ns node) { // 1 daca dreapta, 0 daca stanga
      push(node);
      pns tmp;
      return node == nil? pns{nil, nil}:
               !cb(node)? (tmp = split(cb, node -> l), tmp.r = updnode(node, tmp.r, 0), tmp):
                  (tmp = split(cb, node -> r), tmp.l = updnode(node, tmp.l, 1), tmp);
   }
   template<class CB> pns split(CB&& cb) { return split(cb, root); }
   template<class CB> void walkAll(CB&& cb, ns node) {
      if(node == nil) return;
      push(node);
      cb(node);
      walkAll(cb, node -> l); walkAll(cb, node -> r);
   }
   
   ns root = nil;
};
 
 
int N;
 
const int nmax = 1e6 + 5;
 
pii points[nmax];
vector<int> lefts[nmax * 2];
 
struct Update {
   char type; // modifica X sau Y
   int L;
};
vector<Update> mods;
 
void push(int l, int r, int T, int node = 1, int cl = 0, int cr = sz(mods) - 1) {
   if(cr < l || r < cl) return;
   if(l <= cl && cr <= r) { lefts[node].emplace_back(T); return; }
   int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
   push(l, r, T, L, cl, mid);
   push(l, r, T, R, mid + 1, cr);
}
 
struct Segment {
   int l, r, rmax;
   int ID;
   void pull(const Segment& L, const Segment& R) { rmax = max({r, L.rmax, R.rmax}); }
   void push(const Segment& L, const Segment& R) {;}
};
 
 
struct ZeroZero : private Treap<Segment> {
   void insert(int x, int y, int ID) {
      int l = x, r = N - y;
      auto [L, R] = split([&](ns node) { return node -> data.l <= l; }, root);
      L = merge(L, new Node{Segment{l, r, r, ID}, nil, nil, (int)rng()});
      root = merge(L, R);
   }
   vector<int> extract(int P) {
      auto [focus, outside] = split([&](ns node) { return node -> data.l <= P; }, root);
      vector<int> ids;
      while(focus != nil && focus -> data.rmax >= P) {
         auto [mid, R] = split([&](ns node){ return max(node -> l -> data.rmax, node -> data.r) < P; }, focus);
         auto [single, rest] = split([&, found = 0](ns node) mutable { 
            if(!found) { return (node -> l == nil? (found = 1, 1) : 0); }
            return 0;
                              }, R);
         ids.emplace_back(single -> data.ID);
         focus = merge(mid, rest);
      }
      root = merge(focus, outside);
      return ids;
   }
};
 
struct Point {
   int x, y;
   int lazyx, lazyy;
   int ID;
   void pull(const Point& L, const Point& R) {;}
   void applyX(int lazyx_) { x = max(x, lazyx_); lazyx = max(lazyx_, lazyx); }
   void applyY(int lazyy_) { y = max(y, lazyy_); lazyy = max(lazyy_, lazyy); }
   void push(Point& L, Point& R) {
         L.applyX(lazyx);
         R.applyX(lazyx);
         lazyx = 0;
         L.applyY(lazyy);
         R.applyY(lazyy);
         lazyy = 0;
   }
};
 
struct Scarita : Treap<Point> {
   void insert(int x, int y, int ID) {
      auto [L, R] = split([&](ns node) { return pii{node -> data.x, -node -> data.y} < pii{x, -y}; }, root);
      root = merge(merge(L, new Node{Point{x, y, 0, 0, ID}, nil, nil, (int)rng()}), R);
   }
   tuple<ns, ns, ns> splitRect(int P) {
      auto [L, mid] = split([&](ns node) { return node -> data.y > N - P; }, root);
      auto [want, R] = split([&](ns node) { return node -> data.x <= P; }, mid);
      return tuple<ns, ns, ns>{L, want, R};
   }
   vector<int> extract(int P) {
      vector<int> ids;
      auto [L, mid, R] = splitRect(P);
      walkAll([&](ns node) { points[node -> data.ID] = pii{node -> data.x, node -> data.y}; ids.emplace_back(node -> data.ID); }, mid);
      root = merge(L, R);
      return ids;
   }
   void maxY(int P) {
      auto [L, mid, R] = splitRect(P);
      mid -> data.applyY(N - P);
      root = merge(L, merge(mid, R));
   }
   void maxX(int P) {
      auto [L, mid, R] = splitRect(P);
      mid -> data.applyX(P);
      root = merge(merge(L, mid), R);
   }
};
 
void effectuate(int NODE, int cl, int cr) {
   ZeroZero zerozero;
   for(auto x : lefts[NODE]) zerozero.insert(points[x].first, points[x].second, x);
   Scarita doarX, doarY, ambele;
   for(int i = cl; i <= cr; i++) {
      { // evolutia lui doarY
         if(mods[i].type == 'Y') doarY.maxY(mods[i].L);
         else {
            auto schimb = doarY.extract(mods[i].L);
            for(auto x : schimb) ambele.insert(points[x].first, points[x].second, x);
         }
      }
      { // evolutia lui doarX
         if(mods[i].type == 'X') doarX.maxX(mods[i].L);
         else {
            auto schimb = doarX.extract(mods[i].L);
            for(auto x : schimb) ambele.insert(points[x].first, points[x].second, x);
         }
      }
      { // evolutia lui zero zero
         auto schimb = zerozero.extract(mods[i].L);
         for(auto x : schimb) {
            auto &[a, b] = points[x];
            
            if(mods[i].type == 'X') a = max(a, (b <= N - mods[i].L? mods[i].L : a)), doarX.insert(a, b, x);
            else b = max(b, (a <= mods[i].L? N - mods[i].L : b)), doarY.insert(a, b, x);
         }
      }
      { // evolutia lui ambele
         if(mods[i].type == 'Y') ambele.maxY(mods[i].L);
         else ambele.maxX(mods[i].L);
      }
   }
   
   doarX.walkAll([&](auto node) {
      points[node -> data.ID] = pii{node -> data.x, node -> data.y};
   }, doarX.root);
   doarY.walkAll([&](auto node) {
      points[node -> data.ID] = pii{node -> data.x, node -> data.y};
   }, doarY.root);
   ambele.walkAll([&](auto node) {
      points[node -> data.ID] = pii{node -> data.x, node -> data.y};
   }, ambele.root);
   return;
}
 
void walk(int node = 1, int cl = 0, int cr = sz(mods) - 1) {
   effectuate(node, cl, cr);
   if(cl >= cr) return;
   int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
   walk(L, cl, mid);
   walk(R, mid + 1, cr);
   return;
}
 
signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int m, q;
   cin >> N >> m >> q;
   vector<pii> initstate(m);
   vector<int> spoz(m, 0), querylinks;
   
   for(auto &[a, b] : initstate) { cin >> a >> b; }
   vector<tii> pushes;
   
   
   for(int i = 0, T, upds = 0; i < q; i++) {
      cin >> T;
      if(T == 1) {
         int start, ID = sz(querylinks);
         cin >> start;
         points[ID] = initstate[--start];
         pushes.emplace_back(spoz[start], upds - 1, ID);
         querylinks.emplace_back(ID);
      }
      else if(T == 2) {
         int L; upds++;
         cin >> L;
         mods.emplace_back(Update{'X', N - L});
      }
      else if(T == 3) {
         int L; upds++;
         cin >> L;
         mods.emplace_back(Update{'Y', L});
      }
      else {
         int a, b;
         cin >> a >> b;
         initstate.emplace_back(a, b);
         spoz.emplace_back(upds);
      }
   }
   
   for(auto [l, r, T] : pushes) push(l, r, T);
   walk();
   
   for(auto x : querylinks)
      cout << points[x].first << ' ' << points[x].second << '\n';
   return 0;
}
 
/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49500 KB Output is correct
2 Correct 34 ms 49932 KB Output is correct
3 Correct 19 ms 47960 KB Output is correct
4 Correct 22 ms 49756 KB Output is correct
5 Correct 19 ms 49244 KB Output is correct
6 Correct 21 ms 50524 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4650 ms 576492 KB Output is correct
2 Correct 4767 ms 592716 KB Output is correct
3 Correct 4313 ms 593104 KB Output is correct
4 Correct 2670 ms 579940 KB Output is correct
5 Correct 3863 ms 659716 KB Output is correct
6 Correct 2578 ms 344676 KB Output is correct
7 Correct 4207 ms 591776 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4255 ms 641888 KB Output is correct
2 Correct 4236 ms 650168 KB Output is correct
3 Correct 2529 ms 598232 KB Output is correct
4 Correct 3620 ms 687008 KB Output is correct
5 Correct 3796 ms 633284 KB Output is correct
6 Correct 3969 ms 635616 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4255 ms 641888 KB Output is correct
2 Correct 4236 ms 650168 KB Output is correct
3 Correct 2529 ms 598232 KB Output is correct
4 Correct 3620 ms 687008 KB Output is correct
5 Correct 3796 ms 633284 KB Output is correct
6 Correct 3969 ms 635616 KB Output is correct
7 Correct 5082 ms 605920 KB Output is correct
8 Correct 5070 ms 605260 KB Output is correct
9 Correct 5132 ms 604836 KB Output is correct
10 Correct 2732 ms 587568 KB Output is correct
11 Correct 4277 ms 685984 KB Output is correct
12 Correct 4155 ms 638444 KB Output is correct
13 Correct 4389 ms 641320 KB Output is correct
14 Correct 1012 ms 525124 KB Output is correct
15 Correct 282 ms 92344 KB Output is correct
16 Correct 5030 ms 600336 KB Output is correct
17 Correct 4064 ms 396520 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49500 KB Output is correct
2 Correct 34 ms 49932 KB Output is correct
3 Correct 19 ms 47960 KB Output is correct
4 Correct 22 ms 49756 KB Output is correct
5 Correct 19 ms 49244 KB Output is correct
6 Correct 21 ms 50524 KB Output is correct
7 Correct 4650 ms 576492 KB Output is correct
8 Correct 4767 ms 592716 KB Output is correct
9 Correct 4313 ms 593104 KB Output is correct
10 Correct 2670 ms 579940 KB Output is correct
11 Correct 3863 ms 659716 KB Output is correct
12 Correct 2578 ms 344676 KB Output is correct
13 Correct 4207 ms 591776 KB Output is correct
14 Correct 4255 ms 641888 KB Output is correct
15 Correct 4236 ms 650168 KB Output is correct
16 Correct 2529 ms 598232 KB Output is correct
17 Correct 3620 ms 687008 KB Output is correct
18 Correct 3796 ms 633284 KB Output is correct
19 Correct 3969 ms 635616 KB Output is correct
20 Correct 5082 ms 605920 KB Output is correct
21 Correct 5070 ms 605260 KB Output is correct
22 Correct 5132 ms 604836 KB Output is correct
23 Correct 2732 ms 587568 KB Output is correct
24 Correct 4277 ms 685984 KB Output is correct
25 Correct 4155 ms 638444 KB Output is correct
26 Correct 4389 ms 641320 KB Output is correct
27 Correct 1012 ms 525124 KB Output is correct
28 Correct 282 ms 92344 KB Output is correct
29 Correct 5030 ms 600336 KB Output is correct
30 Correct 4064 ms 396520 KB Output is correct
31 Correct 4296 ms 603812 KB Output is correct
32 Correct 6025 ms 614288 KB Output is correct
33 Correct 3014 ms 566880 KB Output is correct
34 Correct 5241 ms 520760 KB Output is correct
35 Correct 5318 ms 521712 KB Output is correct
36 Correct 2863 ms 588920 KB Output is correct
37 Correct 4299 ms 653580 KB Output is correct
38 Correct 5155 ms 640296 KB Output is correct
39 Correct 5719 ms 667716 KB Output is correct
40 Correct 5656 ms 611424 KB Output is correct