oj.uz

Submission #16770

# Submission time Handle Problem Language Result Execution time Memory
16770 2015-09-24T13:22:22 Z minsu trapezoid (balkan11_trapezoid) C++14
46 / 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;
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 };
	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:44: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:46: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
46.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 Partially correct 0 ms 11576 KB Partially correct
4 Partially correct 0 ms 11708 KB Partially correct
5 Partially correct 3 ms 11840 KB Partially correct
6 Partially correct 6 ms 11840 KB Partially correct
7 Partially correct 3 ms 11972 KB Partially correct
8 Partially correct 9 ms 12104 KB Partially correct
9 Partially correct 16 ms 12500 KB Partially correct
10 Partially correct 46 ms 13560 KB Partially correct
11 Partially correct 46 ms 13952 KB Partially correct
12 Partially correct 136 ms 16328 KB Partially correct
13 Partially correct 169 ms 17252 KB Partially correct
14 Partially correct 176 ms 18176 KB Partially correct
15 Partially correct 226 ms 18716 KB Partially correct
16 Partially correct 233 ms 19280 KB Partially correct
17 Partially correct 226 ms 19760 KB Partially correct
18 Partially correct 216 ms 20024 KB Partially correct
19 Partially correct 229 ms 20688 KB Partially correct
20 Partially correct 279 ms 21092 KB Partially correct