Submission #24895

#TimeUsernameProblemLanguageResultExecution timeMemory
24895dotorya도로 건설 사업 (JOI13_construction)C++14
100 / 100
2086 ms47208 KiB
#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 (stderr)

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);
                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...