oj.uz

Submission #996920

# Submission time Handle Problem Language Result Execution time Memory
996920 2024-06-11T12:27:18 Z cadmiumsky Sweeping (JOI20_sweeping) C++17
100 / 100
 7923 ms 705560 KB 
#pragma GCC target("avx,avx2,sse3,sse4")
#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 24 ms 49500 KB Output is correct
2 Correct 25 ms 50004 KB Output is correct
3 Correct 14 ms 47936 KB Output is correct
4 Correct 24 ms 49752 KB Output is correct
5 Correct 15 ms 49240 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 6113 ms 576968 KB Output is correct
2 Correct 5878 ms 576868 KB Output is correct
3 Correct 5921 ms 575584 KB Output is correct
4 Correct 4690 ms 561636 KB Output is correct
5 Correct 5913 ms 641868 KB Output is correct
6 Correct 3052 ms 336996 KB Output is correct
7 Correct 6860 ms 585928 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6297 ms 646296 KB Output is correct
2 Correct 6130 ms 659076 KB Output is correct
3 Correct 4153 ms 606876 KB Output is correct
4 Correct 5590 ms 705024 KB Output is correct
5 Correct 5407 ms 652584 KB Output is correct
6 Correct 5549 ms 655152 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6297 ms 646296 KB Output is correct
2 Correct 6130 ms 659076 KB Output is correct
3 Correct 4153 ms 606876 KB Output is correct
4 Correct 5590 ms 705024 KB Output is correct
5 Correct 5407 ms 652584 KB Output is correct
6 Correct 5549 ms 655152 KB Output is correct
7 Correct 6927 ms 625120 KB Output is correct
8 Correct 6877 ms 625072 KB Output is correct
9 Correct 6935 ms 624696 KB Output is correct
10 Correct 4521 ms 606716 KB Output is correct
11 Correct 5987 ms 705560 KB Output is correct
12 Correct 5857 ms 657788 KB Output is correct
13 Correct 6298 ms 660336 KB Output is correct
14 Correct 1098 ms 529136 KB Output is correct
15 Correct 332 ms 106480 KB Output is correct
16 Correct 6800 ms 620212 KB Output is correct
17 Correct 5055 ms 376764 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49500 KB Output is correct
2 Correct 25 ms 50004 KB Output is correct
3 Correct 14 ms 47936 KB Output is correct
4 Correct 24 ms 49752 KB Output is correct
5 Correct 15 ms 49240 KB Output is correct
6 Correct 21 ms 50524 KB Output is correct
7 Correct 6113 ms 576968 KB Output is correct
8 Correct 5878 ms 576868 KB Output is correct
9 Correct 5921 ms 575584 KB Output is correct
10 Correct 4690 ms 561636 KB Output is correct
11 Correct 5913 ms 641868 KB Output is correct
12 Correct 3052 ms 336996 KB Output is correct
13 Correct 6860 ms 585928 KB Output is correct
14 Correct 6297 ms 646296 KB Output is correct
15 Correct 6130 ms 659076 KB Output is correct
16 Correct 4153 ms 606876 KB Output is correct
17 Correct 5590 ms 705024 KB Output is correct
18 Correct 5407 ms 652584 KB Output is correct
19 Correct 5549 ms 655152 KB Output is correct
20 Correct 6927 ms 625120 KB Output is correct
21 Correct 6877 ms 625072 KB Output is correct
22 Correct 6935 ms 624696 KB Output is correct
23 Correct 4521 ms 606716 KB Output is correct
24 Correct 5987 ms 705560 KB Output is correct
25 Correct 5857 ms 657788 KB Output is correct
26 Correct 6298 ms 660336 KB Output is correct
27 Correct 1098 ms 529136 KB Output is correct
28 Correct 332 ms 106480 KB Output is correct
29 Correct 6800 ms 620212 KB Output is correct
30 Correct 5055 ms 376764 KB Output is correct
31 Correct 6377 ms 584340 KB Output is correct
32 Correct 7923 ms 593216 KB Output is correct
33 Correct 4840 ms 545600 KB Output is correct
34 Correct 6706 ms 497872 KB Output is correct
35 Correct 6562 ms 497656 KB Output is correct
36 Correct 4927 ms 570144 KB Output is correct
37 Correct 5826 ms 632292 KB Output is correct
38 Correct 6774 ms 620128 KB Output is correct
39 Correct 7237 ms 646752 KB Output is correct
40 Correct 7045 ms 590600 KB Output is correct