Submission #380026

#	Time	Username	Problem	Language	Result	Execution time	Memory
380026		MatheusLealV	Sweeping (JOI20_sweeping)	C++17	0 / 100	2467 ms	91628 KiB

sweeping

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
typedef pair<int, int> pii;
#define N 500050
int n, m, q;
const int inf = (int)(1e9) + 10;
class Treap{
	public:
		struct node{
			int sz, x, y, v, w, lazyX, lazyY;
			int xmin, xmax, ymin, ymax;
			node *l, *r;
			node(int X, int Y){
				sz = 1;
				v = X, w = rand();
				l = r = NULL;
				lazyX = lazyY = -1;
				x = xmin = xmax = X;
				y = ymin = ymax = Y;
			}
		};
		void insert(int idx, int x, int y){
	        node *l = NULL, *r = NULL, *novo = new node (x, y);
	        Split(root, l, r, idx + 1);
	        Merge(root, novo, r);
	        Merge(root, l, root);
    	}
		node *root = NULL;
		void update(int a, int b, int X, int flag){
			node *l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL, *T = NULL;
			Split(root, l1, r1, b + 1);
			Split(l1, l2, r2, a);
			if(flag)r2->lazyX = X;
			else r2->lazyY = X;
			Merge(T, l2, r2);
			Merge(root, T, r1);
		}
		pii query(int a, int b){
			node *l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL, *T = NULL;
			Split(root, l1, r1, b + 1);
			Split(l1, l2, r2, a);
			pii resp =  pii(r2->x, r2->y);
			Merge(T, l2, r2);
			Merge(root, T, r1);
			return resp;
		}

		//retorna o cara mais a direita tal que xi <= XMAX
		int findx(node *&root, int XMAX){
			prop(root);
			// cout<<" XMAX = "<<XMAX<<" | "<<xmin(root)<<"\n";
			if(!root or xmin(root) > XMAX) return 0;
			int p = tam(root->l) + 1, key = root->x;
			if(root->r and key <= XMAX and (!root->l or xmin(root->l)) <= XMAX){
				// cout<<"GO RIGHT\n";
				return p + findx(root->r, XMAX);
			}
			if(key <= XMAX){
				// cout<<"GO MID "<<xmin(root->l)<<"\n";
				return p;
			}
			return findx(root->l, XMAX);
		}
		//retorna o cara mais a esquerda tal que yi <= XMAX
		int findy(node *&root, int XMAX){
			// cout<<"YMAX = "<<XMAX<<"\n";
			prop(root);
			if(!root or ymin(root) > XMAX) return 0;
			int p = tam(root->l) + 1, key = root->y;
			if(root->l and key <= XMAX and (!root->r or ymin(root->r)) <= XMAX) return findy(root->l, XMAX);
			if(key <= XMAX) return p;
			return p + findy(root->r, XMAX);
		}

	private:
		int tam(node *root){return root != NULL? root->sz:0;}
		int xmin(node *&root){return (root?root->xmin:inf);}
		int xmax(node *&root){return (root?root->xmax:-inf);}
		int ymin(node *&root){return (root?root->ymin:inf);}
		int ymax(node *&root){return (root?root->ymax:-inf);}
		void prop(node *&root){
			if(root == NULL) return;
			if(root->l and root->lazyX != -1) root->l->lazyX = root->lazyX, root->l->lazyY = root->lazyY;
			if(root->r and root->lazyY != -1) root->r->lazyX = root->lazyX, root->r->lazyY = root->lazyY;
			if(root->lazyX != -1)root->x = root->lazyX;
			if(root->lazyY != -1)root->y = root->lazyY;
			root->lazyX = root->lazyY = -1;
		}
		void upd(node *&root){
			if(root == NULL) return;
			root->sz = tam(root->l) + tam(root->r) + 1;
			root->xmin = min({xmin(root->l), xmin(root->r),root->x});
			root->xmax = max({xmax(root->l), xmax(root->r),root->x});

			root->ymin = min({ymin(root->l), ymin(root->r),root->y});
			root->ymax = max({ymax(root->l), ymax(root->r),root->y});
		}
	    void Merge(node *&root, node *l, node *r){
	        if(!l or !r) root = (l ? l: r);
	        else{
	            if(l->w > r->w){
	            	prop(l);
	            	Merge(l->r, l->r, r), root = l;
	            }
	            else{
	            	prop(r);
	            	Merge(r->l, l, r->l), root = r;
	            }
	            upd(root);
	        }
	    }
	    void Split(node *root, node *&l, node *&r, int idx){
	        if(!root) l = r = NULL;
	       	else{
	       		prop(root);
	            int p = tam(root->l) + 1;
	            if(p < idx) Split(root->r, root->r, r, idx - p), l = root;
	            else Split(root->l, l, root->l, idx), r = root;
	            upd(root);
	         }
	     }
} good;
pii v[N];
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m>>q;
	for(int i = 1; i <= m; i++){
		cin>>v[i].f>>v[i].s;
		good.insert(i, v[i].f, v[i].s);
	}

	// cout<<good.root->xmin<<" "<<good.root->ymin<<"\n";
	for(int i = 1; i <= q; i++){
		int t;
		cin>>t;
		if(t == 1){
			int p;
			cin>>p;
			auto pos = good.query(p,p);
			cout<<pos.f<<" "<<pos.s<<"\n";
		}
		if(t == 2){
			int l;
			cin>>l;
			int L = good.findy(good.root, l); // menor i, tal que yi <= l
			int R = good.findx(good.root, n-l);// maior i, tal que xi <= n-l
			// cout<<"range222 "<<L<<" "<<R<<"\n";
			if(L > 0 and L <= R)good.update(L, R, n-l,1); // atualiza x para n-l
		}
		if(t == 3){
			int l;
			cin>>l;
			int L = good.findy(good.root, n-l); // menor i, tal que yi <= n-l
			int R = good.findx(good.root, l);// maior i, tal que xi <= x-l
			if(L > 0 and L <= R)good.update(L, R, n-l,0); // atualiza y para n-l
		}
	}
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25