Submission #12969

#TimeUsernameProblemLanguageResultExecution timeMemory
12969ainta도로 건설 사업 (JOI13_construction)C++98
0 / 100
1612 ms60516 KiB
#include<stdio.h> #include<algorithm> #define SZ 1048576 using namespace std; int n, m, Q, D[201000], par[201000]; long long SS[201000]; struct Rectangle{ int x1, x2, y1, y2; }Rect[201000]; struct Seg{ int x, y1, y2, ck; bool operator<(const Seg &p)const{ return x < p.x; } }S[401000]; struct point{ int x, y, num; bool operator<(const point &p)const{ return x != p.x ? x < p.x : y < p.y; } }w[201000], Tw[201000]; struct order{ int y, num; bool operator<(const order &p)const{ return y < p.y; } }Y[601000]; struct Edge{ int a, b, d; bool operator<(const Edge &p)const{ return d < p.d; } }E[401000]; int cnt; struct SegTree{ long long S; int K; }IT[SZ+SZ+2]; void Add2(int nd, int b, int e, int x){ IT[nd].K += x; IT[nd].S += (long long)(e - b + 1)*x; return; } void spread(int nd, int b, int e){ if (!IT[nd].K)return; Add2(nd * 2, b, m, IT[nd].K); Add2(nd * 2 + 1, m + 1, e, IT[nd].K); IT[nd].K = 0; } void Add(int nd, int b, int e, int s, int l, int x){ if (b == s && e == l){ Add2(nd, b, e, x); return; } int m = (b + e) >> 1; spread(nd, b, e); if (s <= m)Add(nd * 2, b, m, s, min(m, l), x); if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x); IT[nd].S = IT[nd * 2].S + IT[nd * 2 + 1].S; } long long Sum(int nd, int b, int e, int s, int l){ long long r = 0; if (b == s && e == l)return IT[nd].S; int m = (b + e) >> 1; spread(nd, b, e); if (s <= m)r += Sum(nd * 2, b, m, s, min(m, l)); if (l > m)r += Sum(nd * 2 + 1, m + 1, e, max(m + 1, s), l); return r; } void Do(){ int i, t = 0, pv; for (i = 1; i <= n; i++){ Y[i].y = w[i].y, Y[i].num = i; Tw[i].x = w[i].x, Tw[i].num = i; } for (i = 1; i <= m; i++){ Y[i + n].y = Rect[i].y1, Y[i + n].num = i + n; Y[i + n + m].y = Rect[i].y2, Y[i + n + m].num = i + n + m; } sort(Y + 1, Y + n + m + m + 1); for (i = 1; i <= n + m + m; i++){ if (i == 1 || Y[i].y != Y[t].y)t = i; if (Y[i].num <= n)Tw[Y[i].num].y = t; else if (Y[i].num <= n + m)Rect[Y[i].num - n].y1 = t; else Rect[Y[i].num - n - m].y2 = t; } for (i = 1; i <= m; i++){ S[i].y1 = S[i + m].y1 = Rect[i].y1, S[i].y2 = S[i + m].y2 = Rect[i].y2; S[i].x = Rect[i].x1, S[i + m].x = Rect[i].x2 + 1; S[i].ck = 1, S[i + m].ck = -1; } sort(Tw, Tw + n + 1); sort(S + 1, S + m + m + 1); pv = 1; for (i = 1; i <= m + m + 1; i++){ while (pv + 1 <= n && (i == m + m + 1 || Tw[pv + 1].x < S[i].x)){ if (Tw[pv].x == Tw[pv + 1].x){ if (!Sum(1, 1, SZ, Tw[pv].y, Tw[pv + 1].y)){ E[cnt].a = Tw[pv].num, E[cnt].b = Tw[pv + 1].num, E[cnt].d = Y[Tw[pv + 1].y].y - Y[Tw[pv].y].y; cnt++; } } pv++; } if (i == m + m + 1)break; Add(1, 1, SZ, S[i].y1, S[i].y2, S[i].ck); } for (i = 1; i <= m; i++){ Rect[i].y1 = Y[Rect[i].y1].y; Rect[i].y2 = Y[Rect[i].y2].y; } } int find(int a){ return a == par[a] ? a : par[a] = find(par[a]); } int main(){ int i, c = 0, a, b, be, ed, mid, r; scanf("%d%d%d", &n, &m, &Q); for (i = 1; i <= n; i++){ scanf("%d%d", &w[i].x, &w[i].y); } for (i = 1; i <= m; i++){ scanf("%d%d%d%d", &Rect[i].x1, &Rect[i].y1, &Rect[i].x2, &Rect[i].y2); } Do(); for (i = 1; i <= n; i++){ swap(w[i].x, w[i].y); } for (i = 1; i <= m; i++){ swap(Rect[i].x1, Rect[i].y1); swap(Rect[i].x2, Rect[i].y2); } Do(); sort(E, E + cnt); for (i = 1; i <= n; i++)par[i] = i; for (i = 0; i < cnt; i++){ a = find(E[i].a), b = find(E[i].b); if (a != b){ par[a] = b; D[++c] = E[i].d; SS[c] = SS[c - 1] + D[c]; } } long long Res; while (Q--){ scanf("%d%d", &a, &b); if (b + c < n){ printf("-1\n"); continue; } be = 1, ed = c, r = 0; while (be <= ed){ mid = (be + ed) >> 1; if (D[mid] <= a){ r = mid; be = mid + 1; } else ed = mid - 1; } if (b < n - r)Res = (long long)b*a + SS[n - b]; else Res = (long long)(n - r)*a + SS[r]; printf("%lld\n", Res); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...