Submission #996825

#	Time	Username	Problem	Language	Result	Execution time	Memory
996825		cadmiumsky	Sweeping (JOI20_sweeping)	C++17	1 / 100	18048 ms	116444 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>;

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) {
      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);
   }
};


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);
}

void effectuate(int node, int cl, int cr) {
   for(int i = cl; i <= cr; i++) {
      for(auto a : lefts[node]) {
         if(mods[i].type == 'X')
            points[a].first = max(points[a].first, (points[a].second <= mods[i].L? N - mods[i].L : points[a].first));
         else
            points[a].second = max(points[a].second, (points[a].first <= mods[i].L? N - mods[i].L : points[a].second));
      }
   }
}

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', 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: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25