Submission #138022


Source Code Expand

#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<complex>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define sz(x) (int)(x).size()
#define popcount __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;

const int MX = 100005, INF = 1000000005;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-10;
const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; //<^>v

int n, m, k;
P p[MX];


bool f(int c){
	int x = 0, h = 0, pi = 0, last = 0;
	priority_queue<int> q;
	while(x+c <= m){
		while(pi < n && p[pi].fi <= x+c){
			q.push(-p[pi++].se);
		}
		if(q.size()){
			int nx = -q.top(); q.pop();
			last = max(last,nx);
			if(nx > x){
				x = min(x+c,nx);
			}
		} else {
			if(x == last) return false;
			x = last;
			h++;
		}
	}
	return (h <= k);
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	
	rep(i,n) scanf("%d%d",&p[i].fi,&p[i].se);
	sort(p,p+n);
	
	int l = 0, r = INF, c;
	while(l+1<r){
		c = l+r>>1;
		if(f(c)) r = c; else l = c;
	}
	
	cout << r << endl;
	
	return 0;
}




Submission Info

Submission Time
Task G - 夏休みの掃除当番
User snuke
Language C++ (G++ 4.6.4)
Score 200
Code Size 1794 Byte
Status AC
Exec Time 553 ms
Memory 2488 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:68:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:70:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Small Large
Score / Max Score 50 / 50 150 / 150
Status
AC × 15
AC × 36
Set Name Test Cases
Small sample01, small-hand00, small-hand01, small-random00, small-random01, small-random02, small-random03, small-random04, small-random05, small-random06, small-random07, small-random08, small-random09, small-random10, small-random11
Large sample02, sample03, large-hand00, large-hand01, large-hand02, large-hand03, large-hand04, large-random00, large-random01, large-random02, large-random03, large-random04, large-random05, large-random06, large-random07, large-random08, large-random09, large-random10, large-random11, large-random12, large-random13, large-random14, small-hand00, small-hand01, small-random00, small-random01, small-random02, small-random03, small-random04, small-random05, small-random06, small-random07, small-random08, small-random09, small-random10, small-random11
Case Name Status Exec Time Memory
large-hand00 AC 23 ms 1564 KB
large-hand01 AC 22 ms 1692 KB
large-hand02 AC 159 ms 1960 KB
large-hand03 AC 169 ms 2216 KB
large-hand04 AC 150 ms 2156 KB
large-random00 AC 432 ms 2392 KB
large-random01 AC 435 ms 2436 KB
large-random02 AC 422 ms 2488 KB
large-random03 AC 372 ms 2328 KB
large-random04 AC 438 ms 2480 KB
large-random05 AC 460 ms 2444 KB
large-random06 AC 358 ms 2356 KB
large-random07 AC 502 ms 2436 KB
large-random08 AC 494 ms 2356 KB
large-random09 AC 480 ms 2352 KB
large-random10 AC 468 ms 2364 KB
large-random11 AC 402 ms 2256 KB
large-random12 AC 553 ms 2408 KB
large-random13 AC 441 ms 2364 KB
large-random14 AC 422 ms 2396 KB
sample01 AC 23 ms 1576 KB
sample02 AC 25 ms 1696 KB
sample03 AC 22 ms 1688 KB
small-hand00 AC 21 ms 1692 KB
small-hand01 AC 158 ms 2216 KB
small-random00 AC 375 ms 2364 KB
small-random01 AC 330 ms 2368 KB
small-random02 AC 373 ms 2368 KB
small-random03 AC 430 ms 2332 KB
small-random04 AC 424 ms 2384 KB
small-random05 AC 432 ms 2328 KB
small-random06 AC 484 ms 2348 KB
small-random07 AC 490 ms 2348 KB
small-random08 AC 481 ms 2356 KB
small-random09 AC 538 ms 2428 KB
small-random10 AC 546 ms 2300 KB
small-random11 AC 545 ms 2260 KB