Submission #306959

# Submission time Handle Problem Language Result Execution time Memory
306959 2020-09-26T15:13:45 Z arnold518 Sweeping (JOI20_sweeping) C++14
0 / 100
16734 ms 1599184 KB
#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)
{
	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 updateH(Node *node, int x, int y, int l, int px, int py)
{
	if(l==0) return;

	int m=l>>1;
	int qx=x+m, qy=y+l-m;
	//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 && l!=1) 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(!V2.empty())
		{
			if(node->rc==NULL) node->rc=new Node();
			for(auto it : V2)
			{
				push(node->rc, qx+1, it.second, it.first);
			}
		}
		if(node->rc!=NULL && l!=1) updateH(node->rc, qx, y, l-m, px, py);
	}
}

void updateV(Node *node, int x, int y, int l, int px, int py)
{
	if(l==0) return;
	
	int m=l>>1;
	int qx=x+m, qy=y+l-m;

	//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 && l!=1) 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(!V2.empty())
		{
			if(node->lc==NULL) node->lc=new Node();
			for(auto it : V2)
			{
				push(node->lc, it.second, qy+1, it.first);
			}
		}
		if(node->lc!=NULL && l!=1) updateV(node->rc, x, qy, m, px, py);
	}
}

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(node!=NULL);
	if(px<=qx && py<=qy)
	{
		push(node, px, py, pnum);
		return;
	}
	if(qy<py)
	{
		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)
	{
		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);
}

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(node->PV[num]!=0);
	if(node->PV[num]==1) return {node->PX[FindX(node, num)], node->PY[FindY(node, num)]};
	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, m, num);
}

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

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

Compilation message

sweeping.cpp: In function 'void updateH(Node*, int, int, int, int, int)':
sweeping.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int i=1; i<V.size(); i++)
      |                 ~^~~~~~~~~
sweeping.cpp: In function 'void updateV(Node*, int, int, int, int, int)':
sweeping.cpp:148:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |    for(int i=1; i<V.size(); i++)
      |                 ~^~~~~~~~~
sweeping.cpp: In function 'pii query(Node*, int, int, int, int)':
sweeping.cpp:224:1: warning: control reaches end of non-void function [-Wreturn-type]
  224 | }
      | ^
sweeping.cpp: In function 'int main()':
sweeping.cpp:229:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  229 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:234:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  234 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:240:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  240 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
sweeping.cpp:244:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  244 |    scanf("%d", &p);
      |    ~~~~~^~~~~~~~~~
sweeping.cpp:251:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  251 |    scanf("%d", &y);
      |    ~~~~~^~~~~~~~~~
sweeping.cpp:258:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  258 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
sweeping.cpp:265:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  265 |    scanf("%d%d", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 16734 ms 1599184 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6691 ms 1231956 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6691 ms 1231956 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -