POI - PA 2008 Diagonals [B]

User:	Chen Kuei-yi (poao899)
Date:	2010-03-30 03:44:39
Points	10
Comment:	Algorithmic Engagements 2008, Round 3
Task:	prz/Diagonals [B]
Date:	2010-03-30 05:04:08
Points:	10/10
Files:	solution

Test case Status Time/Limit Points  0   OK 0.00s/1.00s 0/0  0a   OK 0.00s/1.00s 0/0  1a   OK 0.00s/1.00s 1/1  1b   OK 0.00s/1.00s  2a   OK 0.00s/1.00s 1/1  2b   OK 0.00s/1.00s  3a   OK 0.00s/1.00s 1/1  3b   OK 0.00s/1.00s  3c   OK 0.00s/1.00s  4a   OK 0.01s/1.00s 1/1  4b   OK 0.00s/1.00s  4c   OK 0.01s/1.00s  5a   OK 0.01s/1.00s 1/1  5b   OK 0.00s/1.00s  5c   OK 0.00s/1.00s  6a   OK 0.10s/1.00s 1/1  6b   OK 0.00s/1.00s  6c   OK 0.04s/1.00s  7a   OK 0.31s/3.00s 1/1  7b   OK 0.31s/3.00s  8a   OK 0.09s/1.00s 1/1  8b   OK 0.23s/3.00s  9a   OK 1.06s/8.00s 1/1  9b   OK 0.95s/8.00s  9c   OK 5.40s/8.00s  10a   OK 0.99s/8.00s 1/1  10b   OK 0.90s/8.00s  10c   OK 0.49s/8.00s  10d   OK 5.61s/8.00s

不對啊AC沒道理啊  O(m lg m)sort +O(n)stack

m<=10^7, n<=10^6

怎麼看都不會AC的複雜度

還有拿掉gn跑得比較快ˊˋ


勝利得一點都不開心orz

對了，測資大概灌水兩倍

//*****************************************

#include<algorithm>
#define M 5000010
int n,m,q[M],r;
struct dia{
	int i, j, o;
	void get(int oo){
		scanf("%d%d", &i, &j); o=oo;
		if(i>j){i^=j^=i^=j;}
	}
	bool operator< (const dia &b)const{
		return i<b.i || i==b.i&&j>b.j;
	}
}d[M];
struct dia2{
	int i, j, o;
	void set(int ii, int jj, int oo){
		i=ii; j=jj; o=oo;
	}
	bool operator< (const dia2 &b)const{
		return j<b.j || j==b.j&&i>b.i;
	}
}d2[M];
int main(){
	scanf("%d%d", &n, &m);
	if(m>M)m=M;
	for(int i=0; i<m; i++){
		d[i].get(i+1);
		d2[i].set(d[i].i, d[i].j, i+1);
	}
	std::sort(d, d+m);
	std::sort(d2, d2+m);
	int di=0, di2=0;
	for(int i=1; i<=n; i++){
		for(; di2<m; di2++){
			if(d2[di2].j==i){
				if(q[r-1]== d2[di2].o){
					r--;
				}else{
					printf("%d %d\n",q[r-1], d2[di2].o);
					return 0;
				}
			}else break;
		}
		for(; di<m; di++){
			if(d[di].i==i){
				q[r]= d[di].o;
				r++;
			}else break;
		}
	}
	puts("NIE");
}