oj.uz

Submission #16771

# Submission time Handle Problem Language Result Execution time Memory
16771 2015-09-24T13:23:59 Z minsu trapezoid (balkan11_trapezoid) C++14
100 / 100
 279 ms 21092 KB 
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<int,int> ii;

const int MAXN = 111111;
const int MOD = 30013;

struct TRAPE{
	int a,b,c,d;
	bool operator<(const TRAPE& rhs){
		return b < rhs.b;
	}
};
int N;
TRAPE z[MAXN];
map<int,int> comp;

ii res[8*MAXN];
ii merge( const ii& a, const ii& b ){
	if( a.F == b.F ) return { a.F, ( a.S + b.S )%MOD };
	return (a.F > b.F)? a : b;
}
void update( int i, int I, int J, int p, ii v ){
	if( p < I || J <= p ) return;

	if( J - I == 1 ){
		res[i] = v;
	}else{
		int M = ( I + J ) / 2;
		update( i*2+1, I, M, p, v );
		update( i*2+2, M, J, p, v );
		res[i] = merge( res[i*2+1], res[i*2+2] );
	}
}
ii query( int i, int I, int J, int p ){
	if( J <= p ) return {0,0};
	if( p < I || J - I == 1 ) return res[i];
	int M = ( I + J ) / 2;
	return merge( query(i*2+1, I, M, p) , query(i*2+2, M, J, p ) );
}

int disj[MAXN], disp[MAXN];
int main(){
	scanf("%d",&N); N++; z[0] = { 0,0,0,0 };
	for(int i=1; i<N; i++){
		scanf("%d%d%d%d",&z[i].a, &z[i].b, &z[i].c, &z[i].d );
		comp[ z[i].c ]; comp[ z[i].d ];
	}
	int cp = 0;
	for( auto& it : comp ){
		it.S = cp++;
	}
	for(int i=0; i<N; i++){
		z[i].c = comp[ z[i].c ];
		z[i].d = comp[ z[i].d ];
	}

	sort( z, z+N );
	priority_queue< pair<int,int> > pq;
	for(int i=N-1; i>=0; i--){
		while( !pq.empty() && z[i].b < pq.top().F ){
			int j = pq.top().S;
			update( 0, 0, cp, z[j].c, { disj[j] , disp[j] } );
			pq.pop();
		}
		ii r = query( 0, 0, cp, z[i].d );
		if( r.F == 0 ){
			disj[i] = disp[i] = 1;	
		}else{
			disj[i] = r.F + 1;
			disp[i] = r.S;
		}
		pq.push( { z[i].a, i} );
	}
	printf("%d %d",disj[0]-1,disp[0]);
	return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:46:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N); N++; z[0] = { 0,0,0,0 };
                ^
trapezoid.cpp:48:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&z[i].a, &z[i].b, &z[i].c, &z[i].d );
                                                        ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11576 KB Output is correct
2 Correct 0 ms 11576 KB Output is correct
3 Correct 0 ms 11576 KB Output is correct
4 Correct 0 ms 11708 KB Output is correct
5 Correct 0 ms 11840 KB Output is correct
6 Correct 3 ms 11840 KB Output is correct
7 Correct 6 ms 11972 KB Output is correct
8 Correct 6 ms 12104 KB Output is correct
9 Correct 19 ms 12500 KB Output is correct
10 Correct 39 ms 13560 KB Output is correct
11 Correct 49 ms 13952 KB Output is correct
12 Correct 126 ms 16328 KB Output is correct
13 Correct 149 ms 17252 KB Output is correct
14 Correct 186 ms 18176 KB Output is correct
15 Correct 226 ms 18716 KB Output is correct
16 Correct 233 ms 19280 KB Output is correct
17 Correct 259 ms 19760 KB Output is correct
18 Correct 219 ms 20024 KB Output is correct
19 Correct 236 ms 20688 KB Output is correct
20 Correct 279 ms 21092 KB Output is correct