Submission #996906

#	Time	Username	Problem	Language	Result	Execution time	Memory
996906		cadmiumsky	Sweeping (JOI20_sweeping)	C++17	100 / 100	5673 ms	705788 KiB

sweeping

#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 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25