oj.uz

Submission #24895

# Submission time Handle Problem Language Result Execution time Memory
24895 2017-06-17T05:02:12 Z dotorya 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 2086 ms 47208 KB 
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1E-11;

class Node {
public:
	int mx;
	int v;
	Node() {
		mx = v = 0;
	}
};
Node indt[1100000];
void propagate(int n) {
	indt[2 * n].mx += indt[n].v;
	indt[2 * n].v += indt[n].v;
	indt[2 * n + 1].mx += indt[n].v;
	indt[2 * n + 1].v += indt[n].v;
	indt[n].v = 0;
}
void update(int st, int en, int S, int E, int n, int v) {
	if (st > en) return;
	if (st == S && en == E) {
		indt[n].mx += v;
		indt[n].v += v;
		return;
	}
	propagate(n);

	int M = (S + E) / 2;
	update(st, min(M, en), S, M, 2 * n, v);
	update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
	indt[n].mx = max(indt[2 * n].mx, indt[2 * n + 1].mx);
}
int getmx(int st, int en, int S, int E, int n) {
	if (st > en) return 0;
	if (st == S && en == E) return indt[n].mx;
	propagate(n);

	int M = (S + E) / 2;
	return max(getmx(st, min(M, en), S, M, 2 * n), getmx(max(M + 1, st), en, M + 1, E, 2 * n + 1));
}

int in1[200050][2];
int in2[200050][4];

vector <int> Vx;
vector <int> Vy;

int u[200050];


vector <pair<pii, pii>> Vq;

vector <pair<ll, pii>> Ve;
vector <ll> Vv;
ll sum[200050];

int r[200050];
int root(int x) {
	return (x == r[x]) ? x : (r[x] = root(r[x]));
}
int main() {
	int N, M, C, i, j;
	scanf("%d %d %d", &N, &M, &C);
	for (i = 1; i <= N; i++) {
		scanf("%d %d", &in1[i][0], &in1[i][1]);
	}
	for (i = 1; i <= M; i++) {
		scanf("%d %d %d %d", &in2[i][0], &in2[i][1], &in2[i][2], &in2[i][3]);
		Vx.push_back(in2[i][0]);
		Vx.push_back(in2[i][2]);
		Vy.push_back(in2[i][1]);
		Vy.push_back(in2[i][3]);
	}
	sort(all(Vx));
	sort(all(Vy));
	Vx.erase(unique(all(Vx)), Vx.end());
	Vy.erase(unique(all(Vy)), Vy.end());

	for (i = 1; i <= N; i++) u[i] = i;

	// X same
	sort(u + 1, u + N + 1, [](int a, int b) {
		return pii(in1[a][0], in1[a][1]) < pii(in1[b][0], in1[b][1]);
	});
	for (i = 1; i <= M; i++) {
		Vq.emplace_back(pii(in2[i][0], 1), pii(in2[i][1], in2[i][3]));
		Vq.emplace_back(pii(in2[i][2] + 1, -1), pii(in2[i][1], in2[i][3]));
	}
	sort(all(Vq));
	for (i = 1, j = 0; i < N; i++) {
		if (in1[u[i]][0] != in1[u[i + 1]][0]) continue;
		
		while (j < Vq.size()) {
			if (Vq[j].first.first > in1[u[i]][0]) break;
			int p1 = lower_bound(all(Vy), Vq[j].second.first) - Vy.begin() + 1;
			int p2 = lower_bound(all(Vy), Vq[j].second.second) - Vy.begin();
			update(p1, p2, 1, IT_MAX, 1, Vq[j].first.second);
			j++;
		}
		
		int p1 = lower_bound(all(Vy), in1[u[i]][1] + 1) - Vy.begin();
		p1 = max(p1, 1);
		int p2 = lower_bound(all(Vy), in1[u[i + 1]][1]) - Vy.begin();
		
		if (getmx(p1, p2, 1, IT_MAX, 1) == 0) Ve.emplace_back(in1[u[i + 1]][1] - in1[u[i]][1], pii(u[i], u[i + 1]));
	}
	Vq.clear();
	for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node();
//	for (auto it : Ve) printf("(%d, %d)\n", it.second.first, it.second.second);
//	printf("----------------------------------\n");

	// Y same
	sort(u + 1, u + N + 1, [](int a, int b) {
		return pii(in1[a][1], in1[a][0]) < pii(in1[b][1], in1[b][0]);
	});
	for (i = 1; i <= M; i++) {
		Vq.emplace_back(pii(in2[i][1], 1), pii(in2[i][0], in2[i][2]));
		Vq.emplace_back(pii(in2[i][3] + 1, -1), pii(in2[i][0], in2[i][2]));
	}
	sort(all(Vq));
	for (i = 1, j = 0; i < N; i++) {
		if (in1[u[i]][1] != in1[u[i + 1]][1]) continue;

		while (j < Vq.size()) {
			if (Vq[j].first.first > in1[u[i]][1]) break;
			int p1 = lower_bound(all(Vx), Vq[j].second.first) - Vx.begin() + 1;
			int p2 = lower_bound(all(Vx), Vq[j].second.second) - Vx.begin();
			update(p1, p2, 1, IT_MAX, 1, Vq[j].first.second);
			j++;
		}

		int p1 = lower_bound(all(Vx), in1[u[i]][0] + 1) - Vx.begin();
		p1 = max(p1, 1);
		int p2 = lower_bound(all(Vx), in1[u[i + 1]][0]) - Vx.begin();

		if (getmx(p1, p2, 1, IT_MAX, 1) == 0) Ve.emplace_back(in1[u[i + 1]][0] - in1[u[i]][0], pii(u[i], u[i + 1]));
	}
	Vq.clear();
	for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node();
//	for (auto it : Ve) printf("(%d, %d)\n", it.second.first, it.second.second);

	sort(all(Ve));
	Vv.push_back(0);
	for (i = 1; i <= N; i++) r[i] = i;
	for (auto it : Ve) {
		if (root(it.second.first) == root(it.second.second)) continue;
		Vv.push_back(it.first);
		r[root(it.second.first)] = root(it.second.second);
	}
	while (Vv.size() < N) Vv.push_back(LL_INF);
	for (i = 1; i <= N; i++) sum[i] = min(sum[i - 1] + Vv[i], LL_INF);

	while (C--) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		
		int t3 = N - t2;
		if (Vv[t3] == LL_INF) {
			printf("-1\n");
			continue;
		}

		int st = t3 + 1, en = N - 1, mi, rv = t3;
		while (st <= en) {
			mi = (st + en) / 2;
			if (Vv[mi] < t1) {
				rv = mi;
				st = mi + 1;
			}
			else en = mi - 1;
		}
		printf("%lld\n", sum[rv] + (N - rv) * (ll)t1);
	}
	return 0;
}

Compilation message

construction.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
construction.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 ^
construction.cpp: In function 'int main()':
construction.cpp:143:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < Vq.size()) {
            ^
construction.cpp:174:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < Vq.size()) {
            ^
construction.cpp:200:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (Vv.size() < N) Vv.push_back(LL_INF);
                   ^
construction.cpp:113:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &M, &C);
                               ^
construction.cpp:115:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &in1[i][0], &in1[i][1]);
                                         ^
construction.cpp:118:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &in2[i][0], &in2[i][1], &in2[i][2], &in2[i][3]);
                                                                       ^
construction.cpp:205:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t1, &t2);
                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19056 KB Output is correct
2 Correct 289 ms 24680 KB Output is correct
3 Correct 329 ms 24680 KB Output is correct
4 Correct 406 ms 30828 KB Output is correct
5 Correct 273 ms 26716 KB Output is correct
6 Correct 289 ms 24680 KB Output is correct
7 Correct 219 ms 30828 KB Output is correct
8 Correct 209 ms 26724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1699 ms 34920 KB Output is correct
2 Correct 1829 ms 34920 KB Output is correct
3 Correct 1806 ms 34920 KB Output is correct
4 Correct 1569 ms 34920 KB Output is correct
5 Correct 1109 ms 34920 KB Output is correct
6 Correct 249 ms 26716 KB Output is correct
7 Correct 1759 ms 34920 KB Output is correct
8 Correct 819 ms 47208 KB Output is correct
9 Correct 796 ms 47208 KB Output is correct
10 Correct 596 ms 35940 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 24680 KB Output is correct
2 Correct 639 ms 26724 KB Output is correct
3 Correct 653 ms 24680 KB Output is correct
4 Correct 659 ms 30828 KB Output is correct
5 Correct 459 ms 22640 KB Output is correct
6 Correct 536 ms 26716 KB Output is correct
7 Correct 679 ms 24680 KB Output is correct
8 Correct 689 ms 24680 KB Output is correct
9 Correct 519 ms 30828 KB Output is correct
10 Correct 626 ms 26724 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2086 ms 34920 KB Output is correct
2 Correct 1179 ms 28772 KB Output is correct
3 Correct 1699 ms 34920 KB Output is correct
4 Correct 573 ms 22332 KB Output is correct
5 Correct 1663 ms 34920 KB Output is correct
6 Correct 503 ms 22888 KB Output is correct
7 Correct 1573 ms 34920 KB Output is correct
8 Correct 2039 ms 34920 KB Output is correct
9 Correct 1103 ms 47208 KB Output is correct
10 Correct 929 ms 35940 KB Output is correct
11 Correct 556 ms 27492 KB Output is correct