Submission #307202

#	Time	Username	Problem	Language	Result	Execution time	Memory
307202		arnold518	Sweeping (JOI20_sweeping)	C++14	0 / 100	17326 ms	2097156 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e9;
const int MAXM = 5e5;

int N, M, Q;

struct Node
{
	unordered_map<int, int> PX, PY, QX, QY, PV;
	unordered_map<int, vector<int>> SX, SY;
	map<int, int> MX, MY;
	Node *lc, *rc;
	Node() : lc(NULL), rc(NULL) {}
};
Node *root;

void push(Node *node, int px, int py, int pnum)
{
	assert(px+py<=N);
	assert(node->PX.find(pnum)==node->PX.end());
	node->PX[pnum]=px;
	node->PY[pnum]=py;
	node->PV[pnum]=1;
	node->SX[pnum].push_back(pnum);
	node->SY[pnum].push_back(pnum);
	node->QX[pnum]=pnum;
	node->QY[pnum]=pnum;

	if(node->MX.find(px)==node->MX.end()) node->MX[px]=pnum;
	else
	{
		int t=node->MX[px];
		node->QX[pnum]=t;
		node->SX[t].push_back(pnum);
		node->SX[pnum].pop_back();
	}

	if(node->MY.find(py)==node->MY.end()) node->MY[py]=pnum;
	else
	{
		int t=node->MY[py];
		node->QY[pnum]=t;
		node->SY[t].push_back(pnum);
		node->SY[pnum].pop_back();
	}	
}

int FindX(Node *node, int p)
{
	if(node->QX[p]==p) return p;
	return node->QX[p]=FindX(node, node->QX[p]);
}

int FindY(Node *node, int p)
{
	if(node->QY[p]==p) return p;
	return node->QY[p]=FindX(node, node->QY[p]);
}

void update(Node *node, int x, int y, int l, int px, int py, int pnum)
{
	int m=l>>1;
	int qx=x+m, qy=y+l-m;
	assert(qx+qy==N);
	assert(node!=NULL);
	if(px<=qx && py<=qy)
	{
		//printf("P %d %d Q %d %d / %d\n", px, py, qx, qy, pnum);
		push(node, px, py, pnum);
		return;
	}
	if(qy<py)
	{
		assert(px<qx);
		if(node->lc==NULL) node->lc=new Node();
		node->PV[pnum]=-1;
		update(node->lc, x, qy, m, px, py, pnum);
	}
	else if(qx<px)
	{
		assert(py<qy);
		if(node->rc==NULL) node->rc=new Node();
		node->PV[pnum]=-2;
		update(node->rc, qx, y, l-m, px, py, pnum);	
	}
	else assert(0);
}

void updateH(Node *node, int x, int y, int l, int px, int py)
{
	if(l<=1) return;

	int m=l>>1;
	int qx=x+m, qy=y+l-m;
	assert(qx+qy==N);
	//printf("updateH : x %d y %d qx %d qy %d px %d py %d\n", x, y, qx, qy, px, py);
	if(px<=qx)
	{
		vector<int> V;
		vector<map<int, int>::iterator> VV;
		for(auto it=node->MX.begin(); it!=node->MX.end() && it->first<=px; it++)
		{
			V.push_back(it->second);
			VV.push_back(it);
		}
		for(auto it : VV) node->MX.erase(it);
		if(!V.empty())
		{
			node->MX[px]=V[0];
			node->PX[V[0]]=px;
			for(int i=1; i<V.size(); i++)
			{
				node->QX[V[i]]=V[0];
				if(node->SX[V[0]].size()<node->SX[V[i]].size()) swap(node->SX[V[0]], node->SX[V[i]]);
				while(!node->SX[V[i]].empty())
				{
					node->SX[V[0]].push_back(node->SX[V[i]].back());
					node->SX[V[i]].pop_back();
				}
			}
		}
		if(node->lc!=NULL) updateH(node->lc, x, qy, m, px, py);
	}
	else
	{
		vector<pii> V, V2;
		vector<map<int, int>::iterator> VV;
		for(auto it=node->MY.begin(); it!=node->MY.end() && it->first<=py; it++)
		{
			V.push_back({it->second, it->first});
			VV.push_back(it);
		}
		for(auto it : VV) node->MY.erase(it);
		for(auto it : V) for(auto jt : node->SY[it.first])
		{
			if(node->PV[jt]!=1) continue;
			V2.push_back({jt, it.second});
			node->PV[jt]=-2;
		}
		if(node->rc!=NULL) updateH(node->rc, qx, y, l-m, px, py);
		if(!V2.empty())
		{
			if(node->rc==NULL) node->rc=new Node();
			for(auto it : V2)
			{
				update(node->rc, qx, y, l-m, px, it.second, it.first);
			}
		}
	}
}

void updateV(Node *node, int x, int y, int l, int px, int py)
{
	if(l<=1) return;
	
	int m=l>>1;
	int qx=x+m, qy=y+l-m;
	assert(qx+qy==N);
	//printf("updateH : x %d y %d qx %d qy %d px %d py %d\n", x, y, qx, qy, px, py);
	if(py<=qy)
	{
		vector<int> V;
		vector<map<int, int>::iterator> VV;
		for(auto it=node->MY.begin(); it!=node->MY.end() && it->first<=py; it++)
		{
			V.push_back(it->second);
			VV.push_back(it);
		}
		for(auto it : VV) node->MY.erase(it);
		if(!V.empty())
		{
			node->MY[py]=V[0];
			node->PY[V[0]]=py;
			for(int i=1; i<V.size(); i++)
			{
				node->QY[V[i]]=V[0];
				if(node->SY[V[0]].size()<node->SY[V[i]].size()) swap(node->SY[V[0]], node->SY[V[i]]);
				while(!node->SY[V[i]].empty())
				{
					node->SY[V[0]].push_back(node->SY[V[i]].back());
					node->SY[V[i]].pop_back();
				}
			}
		}
		if(node->rc!=NULL) updateV(node->rc, qx, y, l-m, px, py);
	}
	else
	{
		vector<pii> V, V2;
		vector<map<int, int>::iterator> VV;
		for(auto it=node->MX.begin(); it!=node->MX.end() && it->first<=px; it++)
		{
			V.push_back({it->second, it->first});
			VV.push_back(it);
		}
		for(auto it : VV) node->MX.erase(it);
		for(auto it : V) for(auto jt : node->SX[it.first])
		{
			if(node->PV[jt]!=1) continue;
			V2.push_back({jt, it.second});
			node->PV[jt]=-1;
		}
		if(node->lc!=NULL) updateV(node->lc, x, qy, m, px, py);
		if(!V2.empty())
		{
			if(node->lc==NULL) node->lc=new Node();
			for(auto it : V2)
			{
				update(node->lc, x, qy, m, it.second, py, it.first);
			}
		}
	}
}

pii query(Node *node, int x, int y, int l, int num)
{
	assert(node!=NULL);
	int m=l>>1;
	int qx=x+m, qy=y+l-m;
	assert(qx+qy==N);
	assert(node->PV[num]!=0);
	if(node->PV[num]==1)
	{
		int px=node->PX[FindX(node, num)], py=node->PY[FindY(node, num)];
		//printf("P %d %d Q %d %d XY %d %d / %d\n", px, py, qx, qy, x, y, num);
		assert(px<=qx && py<=qy);
		return {px, py};
	}
	else if(node->PV[num]==-1) return query(node->lc, x, qy, m, num);
	else if(node->PV[num]==-2) return query(node->rc, qx, y, l-m, num);
}

int main()
{
	root=new Node();
	scanf("%d%d%d", &N, &M, &Q); N+=2;

	for(int i=1; i<=M; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y); x++; y++;
		update(root, 0, 0, N, x, y, i);
	}
	while(Q--)
	{
		int t;
		scanf("%d", &t);
		if(t==1)
		{
			int p;
			scanf("%d", &p);
			pii ans=query(root, 0, 0, N, p);
			printf("%d %d\n", ans.first-1, ans.second-1);
		}
		else if(t==2)
		{
			int x, y;
			scanf("%d", &y); y++;
			x=N-y;
			updateH(root, 0, 0, N, x, y);
		}
		else if(t==3)
		{
			int x, y;
			scanf("%d", &x); x++;
			y=N-x;
			updateV(root, 0, 0, N, x, y);	
		}
		else
		{
			int x, y;
			scanf("%d%d", &x, &y); x++; y++; M++;
			update(root, 0, 0, N, x, y, M);
		}
		//printf("DONE\n");
	}
}

Compilation message (stderr)

sweeping.cpp: In function 'void updateH(Node*, int, int, int, int, int)':
sweeping.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |    for(int i=1; i<V.size(); i++)
      |                 ~^~~~~~~~~
sweeping.cpp: In function 'void updateV(Node*, int, int, int, int, int)':
sweeping.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |    for(int i=1; i<V.size(); i++)
      |                 ~^~~~~~~~~
sweeping.cpp: In function 'pii query(Node*, int, int, int, int)':
sweeping.cpp:237:1: warning: control reaches end of non-void function [-Wreturn-type]
  237 | }
      | ^
sweeping.cpp: In function 'int main()':
sweeping.cpp:242:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  242 |  scanf("%d%d%d", &N, &M, &Q); N+=2;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:247:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  247 |   scanf("%d%d", &x, &y); x++; y++;
      |   ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:253:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  253 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
sweeping.cpp:257:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  257 |    scanf("%d", &p);
      |    ~~~~~^~~~~~~~~~
sweeping.cpp:264:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  264 |    scanf("%d", &y); y++;
      |    ~~~~~^~~~~~~~~~
sweeping.cpp:271:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  271 |    scanf("%d", &x); x++;
      |    ~~~~~^~~~~~~~~~
sweeping.cpp:278:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  278 |    scanf("%d%d", &x, &y); x++; y++; M++;
      |    ~~~~~^~~~~~~~~~~~~~~~

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