제출 #104355

#제출 시각아이디문제언어결과실행 시간메모리
104355tieunhi새 집 (APIO18_new_home)C++14
47 / 100
5083 ms284512 KiB
#include <bits/stdc++.h> #define FOR(i, u, v) for (int i = u; i <= v; i++) #define FORD(i, v, u) for (int i = v; i >= u; i--) #define pii pair<int, int> #define mp make_pair #define F first #define S second #define PB push_back #define maxN 1000000000 #define N 300005 using namespace std; struct Store { int x, type, a, b; }; struct Query { int x, t, id; bool operator < (const Query &rhs) const { return x < rhs.x; } }; struct Segment { int L, R, a, b; Segment(int _L=0, int _R=0, int _a=0, int _b=0) : L(_L), R(_R), a(_a), b(_b) {} }; bool cmpSegLR(Segment p, Segment q) { return p.R > q.R || (p.L == q.L && p.L > q.L); } bool cmpSegRL(Segment p, Segment q) { return p.L < q.L || (p.R == q.R && p.R < q.R); } struct SegOnYear { vector<int> t[N << 2]; void update(int l, int r, int id, int x, int y, int val) { if (l > y || r < x) return; if (l >= x && r <= y) { t[id].PB(val); return; } int mid = (r + l)/2; update(l, mid, id*2, x, y, val); update(mid+1, r, id*2+1, x, y, val); } }tSegLR, tSegRL; Store sto[N]; Query que[N]; map<pii, int> maLR, maRL; vector<Segment> segLR, segRL; int n, k, Q, tMax; multiset<int> curSet; vector<pair<int, pii> > allType[N]; int res[N]; int findLef(int x) { auto it = curSet.upper_bound(x); it--; return (*it); } int findRig(int x) { auto it = curSet.upper_bound(x); return (*it); } void addSeg(int L, int R, int time) { int mid = (R + L)/2; maLR[mp(L, mid)] = time; maRL[mp(mid, R)] = time; } void remSeg(int L, int R, int time) { int mid = (R + L)/2; if (time >= maLR[mp(L, mid)]) segLR.PB(Segment(L, mid, maLR[mp(L, mid)], time)); if (time >= maRL[mp(mid, R)]) segRL.PB(Segment(mid, R, maRL[mp(mid, R)], time)); } template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');} template <typename T> inline void writeln(T x){write(x);putchar('\n');} void setup() { read(n); read(k); read(Q); vector<int> allYear; FOR(i, 1, n) { read(sto[i].x); read(sto[i].type); read(sto[i].a); read(sto[i].b); sto[i].x *= 2; } FOR(i, 1, Q) { read(que[i].x); read(que[i].t); que[i].x *= 2; que[i].id = i; allYear.PB(que[i].t); } sort(allYear.begin(), allYear.end()); allYear.resize(unique(allYear.begin(), allYear.end()) - allYear.begin()); FOR(i, 1, n) { sto[i].a = lower_bound(allYear.begin(), allYear.end(), sto[i].a) - allYear.begin() + 1; sto[i].b = upper_bound(allYear.begin(), allYear.end(), sto[i].b) - allYear.begin(); } FOR(i, 1, Q) { que[i].t = lower_bound(allYear.begin(), allYear.end(), que[i].t) - allYear.begin() + 1; } tMax = allYear.size() + 1; sort(que+1, que+Q+1); FOR(i, 1, n) { if (sto[i].a > sto[i].b) continue; int type = sto[i].type; allType[type].PB(mp(sto[i].a, mp(0, sto[i].x))); allType[type].PB(mp(sto[i].b, mp(1, sto[i].x))); } FOR(i, 1, k) { curSet.clear(); curSet.insert(-maxN); curSet.insert(maxN); addSeg(-maxN, maxN, 0); sort(allType[i].begin(), allType[i].end()); for (auto z : allType[i]) { int x = z.S.S; int time = z.F; int type = z.S.F; if (type == 0) { int L = findLef(x), R = findRig(x); remSeg(L, R, time-1); addSeg(L, x, time); addSeg(x, R, time); curSet.insert(x); } else { auto it = curSet.find(x); curSet.erase(it); int L = findLef(x), R = findRig(x); remSeg(L, x, time); remSeg(x, R, time); addSeg(L, R, time+1); } } } sort(segLR.begin(), segLR.end(), cmpSegLR); sort(segRL.begin(), segRL.end(), cmpSegRL); for (int i = 0; i < segLR.size(); i++) { int a = segLR[i].a; int b = segLR[i].b; tSegLR.update(1, tMax, 1, a, b, i); } for (int i = 0; i < segRL.size(); i++) { int a = segRL[i].a; int b = segRL[i].b; tSegRL.update(1, tMax, 1, a, b, i); } } void rayLR(vector<int> seg, vector<int> idQ) { int x0 = maxN, pp = -1; for (int i = idQ.size()-1; i >= 0; i--) { int id = idQ[i]; while (pp < (int)seg.size()-1 && segLR[seg[pp+1]].R >= que[id].x) { pp++; x0 = min(x0, segLR[seg[pp]].L); } if (pp != -1) res[que[id].id] = max(res[que[id].id], que[id].x - x0); } } void rayRL(vector<int> seg, vector<int> idQ) { int y0 = -maxN, pp = -1; for (auto id : idQ) { while (pp < (int)seg.size()-1 && segRL[seg[pp+1]].L <= que[id].x) { pp++; y0 = max(y0, segRL[seg[pp]].R); } if (pp != -1) res[que[id].id] = max(res[que[id].id], y0 - que[id].x); } } void solve(int l, int r, int id, vector<int> curQ) { if (curQ.size() == 0) return; rayLR(tSegLR.t[id], curQ); rayRL(tSegRL.t[id], curQ); if (l == r) return; int mid = (r + l)/2; vector<int> qLef, qRig; for (auto id : curQ) { if (que[id].t <= mid) qLef.PB(id); else qRig.PB(id); } solve(l, mid, id*2, qLef); solve(mid+1, r, id*2+1, qRig); } int cnt[N], impossible[N]; void checkImpossible() { vector<pair<pii, int> > check; FOR(i, 1, n) { check.PB(mp(mp(sto[i].a, 0), sto[i].type)); check.PB(mp(mp(sto[i].b, 2), sto[i].type)); } FOR(i, 1, Q) { check.PB(mp(mp(que[i].t, 1), que[i].id)); } sort(check.begin(), check.end()); int curCnt = 0; for (auto z : check) { int time = z.F.F; int type = z.F.S; int kind = z.S; if (type == 1) impossible[kind] = (curCnt < k); else { if (cnt[kind]) curCnt--; if (type == 0) cnt[kind]++; else cnt[kind]--; if (cnt[kind]) curCnt++; } } } int main() { //freopen("NEWHOME.INP", "r", stdin); //freopen("NEWHOME.OUT", "w", stdout); setup(); vector<int> allQ; FOR(i, 1, Q) allQ.PB(i); solve(1, tMax, 1, allQ); checkImpossible(); FOR(i, 1, Q) { if (impossible[i]) writeln(-1); else writeln(res[i]/2); } }

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'void setup()':
new_home.cpp:142:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < segLR.size(); i++) {
                     ~~^~~~~~~~~~~~~~
new_home.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < segRL.size(); i++) {
                     ~~^~~~~~~~~~~~~~
new_home.cpp: In function 'void checkImpossible()':
new_home.cpp:211:13: warning: unused variable 'time' [-Wunused-variable]
         int time = z.F.F;
             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...