Submission #587871

#	Time	Username	Problem	Language	Result	Execution time	Memory
587871		pooyashams	Sweeping (JOI20_sweeping)	C++17	0 / 100	18106 ms	737984 KiB

sweeping

#pragma GCC optimize("unroll-loops,Ofast")
#define _GLIBCXX_DEBUG
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
//#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 1.5e6+10;
const int inf = 1e9+69;

#define lc (v<<1)
#define rc (lc|1)

int vrt[maxn];
int trnum[maxn];

struct ltree
{
	vector<int> vals; // min tree, sz = 2*n
	vector<int> lazy;
	vector<int> nid;
	int n;
	ltree()
	{
		n = 0;
	}
	inline void upd(int v)
	{
		if(v < n)
			vals[v] = min(vals[lc], vals[rc]);
	}
	inline void put(int v, int x)
	{
		vals[v] = max(vals[v], x);
		lazy[v] = max(lazy[v], x);
	}
	inline void shift(int v)
	{
		if(lazy[v] == 0) return;
		if(v < n)
		{
			put(lc, lazy[v]);
			put(rc, lazy[v]);
		}
		lazy[v] = 0;
	}
	inline void relax(int v)
	{
		stack<int> prs;
		int x = v;
		while(x > 0)
		{
			prs.push(x);
			x >>= 1;
		}
		while(!prs.empty())
		{
			shift(prs.top());
			prs.pop();
		}
		while(v > 0)
		{
			upd(v);
			v >>= 1;
		}
	}
	inline int get(int id)
	{
		relax(vrt[id]);
		return vals[vrt[id]];
	}
	inline int get_min() // id
	{
		//if(n == 0)
		//	return inf;
		int mn = vals[1];
		int v = 1;
		while(v < n)
		{
			if(vals[lc] == mn)
				v = lc;
			else
				v = rc;
		}
		return nid[v];
	}
	inline void ass_max(int x)
	{
		put(1, x);
	}
	inline void add(int id, int x)
	{
		//n++;
		if(n == 0)
		{
			vals = {-1, x};
			lazy = {-1, 0};
			nid = {-1, id};
			n = 1;
			vrt[id] = 1;
		}
		else
		{
			relax(n);
			//
			vals.push_back(vals[n]);
			vals.push_back(x);
			lazy.push_back(0);
			lazy.push_back(0);
			//
			nid.push_back(nid[n]);
			nid.push_back(id);
			nid[n] = -1;
			//
			vrt[nid[2*n]] = 2*n;
			vrt[nid[2*n+1]] = 2*n+1;
			//
			n++;
			relax(n-1);
		}
	}
	inline void remove(int id) // id should be in tree
	{
		if(n == 1)
		{
			vals = vector<int>();
			lazy = vector<int>();
			nid = vector<int>();
			n = 0;
		}
		else
		{
			//cerr << "removing " << id << endl;
			int v = vrt[id];
			int x = 2*n-1;
			relax(v);
			relax(x);
			//cerr << x << " " << v << " --- " << vals[0] << " " << vals[1] << " " << vals[2] << " " << vals[3] << endl;
			//
			swap(vals[v], vals[x]);
			swap(nid[v], nid[x]);
			vrt[nid[v]] = v;
			vrt[nid[x]] = x;
			//
			vals[n-1] = vals[x-1];
			nid[n-1] = nid[x-1];
			vrt[nid[n-1]] = n-1;
			//
			vals.pop_back(); vals.pop_back();
			lazy.pop_back(); lazy.pop_back();
			nid.pop_back(); nid.pop_back();
			//cerr << x << " " << v << " --- " << vals[0] << " " << vals[1] << endl;
			//
			n--;
			relax(n-1);
			if(v < 2*n)
				relax(v);
			//cerr << x << " " << v << " --- " << vals[0] << " " << vals[1] << " " << vals[2] << " " << vals[3] << endl;
		}
	}
} trees[maxn][2];

map<int, int> trid;
set<int> tempty;

bool pdone[maxn];
pii ppos[maxn];

#define X first
#define Y second

int H;

inline void add_tree(int id, pii pos, int v)
{
	if(trid.find(v) == trid.end())
	{
		trid[v] = *tempty.begin();
		tempty.erase(tempty.begin());
	}
	int x = trid[v];
	trees[x][0].add(id*2, pos.X);
	trees[x][1].add(id*2+1, pos.Y);
	trnum[id] = x;
}

void add_seg(int x, int y, int h, int id, pii pos, int v)
{
	int nx = x + h/2 + 1;
	int ny = y + (h+1)/2 + 1;
	if(h == 0)
	{
		//cerr << "ridim0" << endl;
	}
	if(h == 1)
	{
		if(pos.X == x and pos.Y == y)
			add_tree(id, pos, v);
		//else if(pos.X == x+1 and pos.Y == y)
		//	add_tree(id, pos, lc);
		//else if(pos.X == x and pos.Y == y+1)
		//	add_tree(id, pos, rc);
		else
			cerr << "ridim" << endl;
		//return;
	}
	if(pos.X >= nx)
	{
		add_seg(nx, y, (h+1)/2 - 1, id, pos, lc);
	}
	else if(pos.Y >= ny)
	{
		add_seg(x, ny, h/2 - 1, id, pos, rc);
	}
	else
	{
		//cerr << v << endl;
		add_tree(id, pos, v);
	}
}

inline void add_dust(int p, int x, int y)
{
	if(x+y == H)
	{
		pdone[p] = true;
		ppos[p] = pii(x, y);
	}
	else
	{
		add_seg(0, 0, H, p, pii(x, y), 1);
	}
}

inline pii get_dust(int p)
{
	if(pdone[p])
		return ppos[p];
	int x = trnum[p];
	return pii(trees[x][0].get(p*2), trees[x][1].get(p*2+1));
}

inline void vert(int x, int y, int h, int l, int v)
{
	if(l < 0) return;
	if(trid.find(v) != trid.end())
	{
		int z = trid[v];
		if( l >= (h/2) )
		{
			trees[z][1].ass_max(y+h-l);
		}
		else
		{
			while(trees[z][0].n > 0 and trees[z][0].vals[1] <= x+l)
			{
				int p = trees[z][0].get_min() / 2;
				pii pos(trees[z][0].get(p*2), y+h-l);
				trees[z][0].remove(p*2);
				trees[z][1].remove(p*2+1);
				//add_tree(p, pos, rc);
				if(l == 0)
				{
					pdone[p] = true;
					ppos[p] = pii(x, y+h);
				}
				else
				{
					add_dust(p, pos.X, pos.Y);
				}
			}
			if(trees[z][0].n == 0)
			{
				tempty.insert(z);
				trid.erase(v);
			}
		}
	}
	if( l > (h/2) )
	{
		vert(x + (h/2) + 1, y, ((h+1)/2)-1, l-h/2-1, lc);
	}
	if( l < (h/2) )
	{
		vert(x, y+(h+1)/2+1, h/2-1, l, rc);
	}
}

inline void horz(int x, int y, int h, int l, int v)
{
	if(l < 0) return;
	if(trid.find(v) != trid.end())
	{
		int z = trid[v];
		if( l >= (h+1)/2 )
		{
			trees[z][0].ass_max(x+h-l);
		}
		else
		{
			while(trees[z][1].n > 0 and trees[z][1].vals[1] <= y+l)
			{
				int p = trees[z][1].get_min() / 2;
				pii pos(x+h-l, trees[z][1].get(p*2+1));
				trees[z][0].remove(p*2);
				trees[z][1].remove(p*2+1);
				//add_tree(p, pos, lc);
				if(l == 0)
				{
					pdone[p] = true;
					ppos[p] = pii(x+h, y);
				}
				else
				{
					add_dust(p, pos.X, pos.Y);
				}
			}
			if(trees[z][1].n == 0)
			{
				tempty.insert(z);
				trid.erase(v);
			}
		}
	}
	if( l > (h+1)/2 )
	{
		horz(x, y+(h+1)/2+1, h/2-1, l-(h+1)/2-1, rc);
	}
	if( l < (h+1)/2 )
	{
		horz(x + (h/2) + 1, y, ((h+1)/2)-1, l, lc);
	}
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cerr << sizeof(vector<int>) << endl;
	//cerr << sizeof(ltree) << endl;
	vector<int> tmp(maxn);
	iota(tmp.begin(), tmp.end(), 0);
	tempty = set<int>(tmp.begin(), tmp.end());
	int n, q; cin >> H >> n >> q;
	for(int i = 0; i < n; i++)
	{
		//cerr << i << endl;
		int x,y; cin >> x >> y;
		add_dust(i, x, y);
	}
	int c = n;
	while(q--)
	{
		int t; cin >> t;
		if(t == 1)
		{
			int p; cin >> p;
			p--;
			pii ans = get_dust(p);
			cout << ans.first << " " << ans.second << endl;
		}
		else if(t == 2)
		{
			int l; cin >> l;
			//cerr << "horz " << 5-q << endl;
			horz(0, 0, H, l, 1);
			//for(int i = 0; i < c; i++)
			//{
			//	pii p = get_dust(i);
			//	cerr << p.first << " " << p.second << endl;
			//}
			//cerr << "----" << endl;
		}
		else if(t == 3)
		{
			int l; cin >> l;
			vert(0, 0, H, l, 1);
		}
		else // t == 4
		{
			int x,y; cin >> x >> y;
			add_dust(c++, x, y);
		}
	}
	return 0;
}

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