oj.uz

Submission #996906

# Submission time Handle Problem Language Result Execution time Memory
996906 2024-06-11T12:16:41 Z cadmiumsky Sweeping (JOI20_sweeping) C++17
100 / 100
 5673 ms 705788 KB 
#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 16 ms 49752 KB Output is correct
2 Correct 17 ms 50008 KB Output is correct
3 Correct 10 ms 47960 KB Output is correct
4 Correct 17 ms 49720 KB Output is correct
5 Correct 11 ms 49244 KB Output is correct
6 Correct 15 ms 50520 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4217 ms 588324 KB Output is correct
2 Correct 3988 ms 597856 KB Output is correct
3 Correct 4013 ms 597600 KB Output is correct
4 Correct 2266 ms 580424 KB Output is correct
5 Correct 3427 ms 662372 KB Output is correct
6 Correct 2139 ms 345596 KB Output is correct
7 Correct 4035 ms 597192 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4176 ms 640356 KB Output is correct
2 Correct 4128 ms 659832 KB Output is correct
3 Correct 2467 ms 607404 KB Output is correct
4 Correct 3564 ms 705788 KB Output is correct
5 Correct 3741 ms 652784 KB Output is correct
6 Correct 3991 ms 655764 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4176 ms 640356 KB Output is correct
2 Correct 4128 ms 659832 KB Output is correct
3 Correct 2467 ms 607404 KB Output is correct
4 Correct 3564 ms 705788 KB Output is correct
5 Correct 3741 ms 652784 KB Output is correct
6 Correct 3991 ms 655764 KB Output is correct
7 Correct 4784 ms 625376 KB Output is correct
8 Correct 4969 ms 625448 KB Output is correct
9 Correct 4777 ms 624768 KB Output is correct
10 Correct 2539 ms 607024 KB Output is correct
11 Correct 3854 ms 705612 KB Output is correct
12 Correct 4122 ms 658152 KB Output is correct
13 Correct 4406 ms 660776 KB Output is correct
14 Correct 931 ms 529080 KB Output is correct
15 Correct 279 ms 106480 KB Output is correct
16 Correct 4314 ms 620192 KB Output is correct
17 Correct 3353 ms 396684 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 49752 KB Output is correct
2 Correct 17 ms 50008 KB Output is correct
3 Correct 10 ms 47960 KB Output is correct
4 Correct 17 ms 49720 KB Output is correct
5 Correct 11 ms 49244 KB Output is correct
6 Correct 15 ms 50520 KB Output is correct
7 Correct 4217 ms 588324 KB Output is correct
8 Correct 3988 ms 597856 KB Output is correct
9 Correct 4013 ms 597600 KB Output is correct
10 Correct 2266 ms 580424 KB Output is correct
11 Correct 3427 ms 662372 KB Output is correct
12 Correct 2139 ms 345596 KB Output is correct
13 Correct 4035 ms 597192 KB Output is correct
14 Correct 4176 ms 640356 KB Output is correct
15 Correct 4128 ms 659832 KB Output is correct
16 Correct 2467 ms 607404 KB Output is correct
17 Correct 3564 ms 705788 KB Output is correct
18 Correct 3741 ms 652784 KB Output is correct
19 Correct 3991 ms 655764 KB Output is correct
20 Correct 4784 ms 625376 KB Output is correct
21 Correct 4969 ms 625448 KB Output is correct
22 Correct 4777 ms 624768 KB Output is correct
23 Correct 2539 ms 607024 KB Output is correct
24 Correct 3854 ms 705612 KB Output is correct
25 Correct 4122 ms 658152 KB Output is correct
26 Correct 4406 ms 660776 KB Output is correct
27 Correct 931 ms 529080 KB Output is correct
28 Correct 279 ms 106480 KB Output is correct
29 Correct 4314 ms 620192 KB Output is correct
30 Correct 3353 ms 396684 KB Output is correct
31 Correct 3983 ms 604180 KB Output is correct
32 Correct 5673 ms 613512 KB Output is correct
33 Correct 2796 ms 564916 KB Output is correct
34 Correct 4980 ms 520436 KB Output is correct
35 Correct 4985 ms 519888 KB Output is correct
36 Correct 2738 ms 588500 KB Output is correct
37 Correct 3980 ms 654656 KB Output is correct
38 Correct 4888 ms 641812 KB Output is correct
39 Correct 5592 ms 666464 KB Output is correct
40 Correct 5467 ms 613444 KB Output is correct