제출 #49642

#제출 시각아이디문제언어결과실행 시간메모리
49642SpaimaCarpatilor새 집 (APIO18_new_home)C++17
5 / 100
5058 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; int N, K, Q, timeCount, x[300009], type[300009], a[300009], b[300009], location[300009], when[300009], ans[300009]; const int INF = 5e8, maxX = 1e8; int changesLine = 0; vector < pair < int*, int > > changes[20]; vector < multiset < int > > S; vector < pair < int, int > > setChanges[20]; void update (int &x, int y) { if (y > x) changes[changesLine].push_back ({&x, x}), x = y; } int emptySets = 0; void rollBack (int id) { reverse (changes[id].begin (), changes[id].end ()); for (auto it : changes[id]) *it.first = it.second; changes[id].clear (); for (auto it : setChanges[id]) emptySets -= S[it.first].empty (), S[it.first].insert (it.second); setChanges[id].clear (); } const int maxSize = 8000009; int cntNodes[2], aint[2][maxSize], leftSon[2][maxSize], rightSon[2][maxSize]; void update (int lin, int nod, int st, int dr, int x, int y, int lazyVal) { if (nod == 1) { if (x < 1) { if (lin == 0) lazyVal += 1 - x; else lazyVal -= (1 - x); x = 1; } if (y < x) return ; if (y > maxX) y = maxX; //printf ("line %d [%d, %d] shift %d\n", lin, x, y, lazyVal); } if (x <= st && dr <= y) { if (lin == 0) update (aint[lin][nod], lazyVal + st - x); else update (aint[lin][nod], lazyVal - (st - x)); return ; } int mij = (st + dr) >> 1, f1 = leftSon[lin][nod], f2 = rightSon[lin][nod]; if (f1 == 0) f1 = leftSon[lin][nod] = ++cntNodes[lin], aint[lin][f1] = -INF; if (f2 == 0) f2 = rightSon[lin][nod] = ++cntNodes[lin], aint[lin][f2] = -INF; update (aint[lin][f1], aint[lin][nod]); if (lin == 0) update (aint[lin][f2], aint[lin][nod] + mij + 1 - st); else update (aint[lin][f2], aint[lin][nod] - (mij + 1 - st)); if (x <= mij) update (lin, f1, st, mij, x, y, lazyVal); if (mij < y) update (lin, f2, mij + 1, dr, x, y, lazyVal); } int query (int lin, int nod, int st, int dr, int pos) { if (nod == 0) return -INF; if (st == dr) return aint[lin][nod]; int mij = (st + dr) >> 1, ans = aint[lin][nod]; if (lin == 0) ans += pos - st; else ans -= (pos - st); if (pos <= mij) ans = max (ans, query (lin, leftSon[lin][nod], st, mij, pos)); else ans = max (ans, query (lin, rightSon[lin][nod], mij + 1, dr, pos)); return ans; } int maxDist (int x) { int v1 = query (0, 1, 1, maxX, x), v2 = query (1, 1, 1, maxX, x); return max (v1, v2); } void addSegm (int x0, int x2) { int mid = (x0 + x2) / 2; update (0, 1, 1, maxX, x0, mid, 0); update (1, 1, 1, maxX, mid + 1, x2, x2 - (mid + 1)); } void delPoint (int type, int x) { //printf ("del (%d, %d)\n", type, x); auto it = S[type].lower_bound (x), it0 = it, it2 = it; int x0, x2; if (it0 == S[type].begin ()) x0 = -INF; else it0 --, x0 = *it0; it2 ++; if (it2 == S[type].end ()) x2 = +INF; else x2 = *it2; if (x0 != x && x2 != x) addSegm (x0, x2); setChanges[changesLine].push_back ({type, x}); S[type].erase (it), emptySets += S[type].empty (); } void init () { aint[0][1] = aint[1][1] = -INF; cntNodes[0] = cntNodes[1] = 1; for (int i=1; i<=K; i++) { emptySets += S[i].empty (); int lastX = -INF; for (auto it : S[i]) addSegm (lastX, it), lastX = it; addSegm (lastX, +INF); } changes[changesLine].clear (); } map < int, int > normT; void normalize () { for (auto &it : normT) it.second = ++timeCount; for (int i=1; i<=Q; i++) when[i] = normT[when[i]]; for (int i=1; i<=N; i++) a[i] = normT[a[i]], b[i] = normT[b[i]]; } vector < vector < int > > delList, qry; void addToDelList (int nod, int st, int dr, int x, int y, int val) { if (x <= st && dr <= y) { //printf ("add %d to delList[%d]\n", val, nod); delList[nod].push_back (val); return ; } int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1; if (x <= mij) addToDelList (f1, st, mij, x, y, val); if (mij < y) addToDelList (f2, mij + 1, dr, x, y, val); } void buildDelList () { delList.resize (4 * (timeCount + 1)); for (int i=1; i<=N; i++) { if (a[i] > 1) addToDelList (1, 1, timeCount, 1, a[i] - 1, i); if (b[i] < timeCount) addToDelList (1, 1, timeCount, b[i] + 1, timeCount, i); } } void solveDC (int nod, int st, int dr) { changesLine ++; for (auto it : delList[nod]) { delPoint (type[it], x[it]); //printf ("->size=%d\n", S[1].size ()); } if (st == dr) { for (auto it : qry[st]) { //printf ("solve %d (time=%d, location=%d)\n", it, when[it], location[it]); if (emptySets > 0) ans[it] = -1; else ans[it] = maxDist (location[it]); } } else { int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1; solveDC (f1, st, mij); solveDC (f2, mij + 1, dr); } /* for (auto it : delList[nod]) printf ("add (%d, %d)\n", type[it], x[it]);*/ // bool needToPrint = (setChanges[changesLine].size () > 0); rollBack (changesLine), changesLine --; // if (needToPrint) printf ("->size=%d\n", S[1].size ()); } int main () { //freopen ("input", "r", stdin); //freopen ("output", "w", stdout); scanf ("%d %d %d", &N, &K, &Q), S.resize (K + 1); for (int i=1; i<=N; i++) scanf ("%d %d %d %d", &x[i], &type[i], &a[i], &b[i]), S[type[i]].insert (x[i]), normT[a[i]] = 1, normT[b[i]] = 1; init (); /*printf ("%d\n", maxDist (5)); return 0;*/ for (int i=1; i<=Q; i++) scanf ("%d %d", &location[i], &when[i]), normT[when[i]] = 1; normalize (); buildDelList (); qry.resize (timeCount + 1); for (int i=1; i<=Q; i++) qry[when[i]].push_back (i); solveDC (1, 1, timeCount); for (int i=1; i<=Q; i++) printf ("%d\n", ans[i]); return 0; }

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

new_home.cpp: In function 'int main()':
new_home.cpp:200:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d %d", &N, &K, &Q), S.resize (K + 1);
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
new_home.cpp:203:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d %d", &x[i], &type[i], &a[i], &b[i]),
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     S[type[i]].insert (x[i]), normT[a[i]] = 1, normT[b[i]] = 1;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:208:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &location[i], &when[i]), normT[when[i]] = 1;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
#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...