제출 #170884

#제출 시각아이디문제언어결과실행 시간메모리
170884songc가로등 (APIO19_street_lamps)C++14
0 / 100
138 ms10852 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; int N, Q; int A[303030]; bool chk[303030]; int ans[303030]; struct Sq{ int x, y, t; bool operator<(const Sq &r)const{ if (x == r.x) return y < r.y; return x < r.x; } }; set<Sq> S; vector<Sq> V, L; int T[303030]; void update(int k, int v){ while (k<=N){ T[k] += v; k += k & -k; } } int read(int k){ int ret; while (k){ ret += T[k]; k ^= k & -k; } return ret; } void sweep(){ for (Sq it : L){ if (it.t < 0) ans[-it.t] += read(it.y); else if (it.x <= it.y){ update(it.x, it.t); update(it.y+1, -it.t); } else{ update(it.y, it.t); update(it.x, -it.t); } } for (Sq it : L){ if (it.t < 0) continue; if (it.x <= it.y){ update(it.x, -it.t); update(it.y+1, it.t); } else{ update(it.y, -it.t); update(it.x, it.t); } } } void DNC(int s, int e){ if (s >= e) return; int mid = (s+e)/2; DNC(s, mid); DNC(mid+1, e); for (int i=s; i<=mid; i++) if (V[i].t > 0){ L.push_back((Sq){V[i].x, V[i].y, V[i].t}); L.push_back((Sq){V[i].y+1, V[i].x, V[i].t}); } for (int i=mid+1; i<=e; i++) if (V[i].t < 0) L.push_back((Sq){V[i].x, V[i].y, V[i].t}); sort(L.begin(), L.end(), [&](Sq a, Sq b){ if (a.x == b.x) return a.t > b.t; return a.x < b.x; }); sweep(); L.clear(); } int main(){ scanf("%d %d", &N, &Q); int s=0; for (int i=1; i<=N; i++){ scanf("%1d", &A[i]); if (A[i] && !s) s = i; if (!A[i] && s) { S.insert((Sq){s, i-1, 0}); s = 0; } } if (s) S.insert((Sq){s, N, 0}); char str[10]; for (int i=1; i<=Q; i++){ scanf("%s", str+1); if (str[1] == 't'){ int k; scanf("%d", &k); if (A[k]){ auto it = --S.lower_bound((Sq){k, N+1, 0}); Sq a = *it; S.erase(it); V.push_back((Sq){a.x, a.y, i-a.t}); if (a.x != k) S.insert((Sq){a.x, k-1, i}); if (a.y != k) S.insert((Sq){k+1, a.y, i}); A[k] = 0; } else{ auto it = S.lower_bound((Sq){k, N+1, 0}); if (A[k-1] && A[k+1]){ auto pr = it; Sq a = *it; Sq b = *(--pr); S.erase(it), S.erase(pr); V.push_back((Sq){a.x, a.y, i-a.t}); V.push_back((Sq){b.x, b.y, i-b.t}); S.insert((Sq){b.x, a.y, i}); } else if (A[k-1]){ Sq a = *(--it); S.erase(it); V.push_back((Sq){a.x, a.y, i-a.t}); S.insert((Sq){a.x, a.y+1, i}); } else if (A[k+1]){ Sq a = *it; S.erase(it); V.push_back((Sq){a.x, a.y, i-a.t}); S.insert((Sq){a.x-1, a.y, i}); } else S.insert((Sq){k, k, i}); A[k] = 1; } } else{ int x, y; scanf("%d %d", &x, &y); y--; chk[i] = true; if (A[x]){ auto it = --S.lower_bound((Sq){x, N+1, 0}); if (it->y >= y) ans[i] += i - it->t; } V.push_back((Sq){x, y, -i}); } } for (int i=1; i<=Q; i++) if (chk[i]) printf("%d\n", ans[i]); return 0; }

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

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%1d", &A[i]);
   ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str+1);
   ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &k);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:139:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &x, &y);
    ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int read(int)':
street_lamps.cpp:36:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ret;
         ^~~
street_lamps.cpp: In function 'void sweep()':
street_lamps.cpp:41:28: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (it.t < 0) ans[-it.t] += read(it.y);
                 ~~~~~~~~~~~^~~~~~~~~~~~~
#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...