제출 #555699

#제출 시각아이디문제언어결과실행 시간메모리
555699Zanite가로등 (APIO19_street_lamps)C++17
100 / 100
3894 ms286604 KiB
// "I assure you that you guys won't make it to the top 4" // - Tzaph, 21 December 2021 #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define ll long long #define ld long double #define si short int #define i8 __int128 #define pii pair<int, int> #define pll pair<ll, ll> #define pld pair<ld, ld> #define psi pair<si, si> #define pi8 pair<i8, i8> #define pq priority_queue #define fi first #define se second #define sqr(x) ((x)*(x)) #define pow2(x) (1ll << (x)) #define debug(x) cout << #x << " = " << (x) << '\n' #define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n' #define yume using #define wo namespace #define kanaeyo std #define nazotte __gnu_pbds yume wo kanaeyo; yume wo nazotte; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;} template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;} template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;} template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;} template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;} template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;} const ll ModA = 998244353; const ll ModC = 1e9 + 7; const ll INF = 1e18; const ll iINF = 1e9; const ld EPS = 1e-9; const ld iEPS = 1e-6; const int maxN = 3e5 + 5; struct FenwickTree { ll sz; vector<ll> BIT; FenwickTree(ll _sz) { sz = _sz; BIT.assign(_sz+1, 0); } void update(ll idx, ll val) { for (; idx <= sz; idx += (idx & -idx)) { BIT[idx] += val; } } ll sum(ll idx) { ll ret = 0; idx = min(idx, sz); for (; idx > 0; idx -= (idx & -idx)) { ret += BIT[idx]; } return ret; } ll query(ll l, ll r) { return sum(r) - sum(l-1); } }; struct FenwickTree2D { ll sz; vector<FenwickTree> inner; vector<vector<ll>> pos; FenwickTree2D(ll _sz) { sz = _sz; pos.assign(_sz + 1, vector<ll>(0)); } void addPos(ll d1, ll d2) { for (; d1 <= sz; d1 += (d1 & -d1)) { pos[d1].push_back(d2); } } void build() { for (ll i = 0; i <= sz; i++) { sort(pos[i].begin(), pos[i].end()); pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end()); inner.push_back(FenwickTree(pos[i].size())); } } void update(ll d1, ll d2, ll val) { for (; d1 <= sz; d1 += (d1 & -d1)) { ll d2_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2) - pos[d1].begin() + 1; //cout << d1 << ' ' << d2 << ' ' << d2_compressed << '\n'; inner[d1].update(d2_compressed, val); } } ll sum(ll d1, ll d2l, ll d2r) { ll ret = 0; for (; d1 > 0; d1 -= (d1 & -d1)) { ll d2l_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2l) - pos[d1].begin() + 1; ll d2r_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2r) - pos[d1].begin() + 1; //cout << d1 << ' ' << d2l_compressed << ' ' << d2r_compressed << '\n'; ret += inner[d1].query(d2l_compressed, d2r_compressed); } return ret; } ll query(ll d1l, ll d1r, ll d2l, ll d2r) { //cout << sum(d1r, d2l, d2r) << ' ' << sum(d1l-1, d2l, d2r) << '\n'; return sum(d1r, d2l, d2r) - sum(d1l-1, d2l, d2r); } void printPos() { for (ll i = 1; i <= sz; i++) { cout << i << ": "; for (auto j : pos[i]) {cout << j << " ";} cout << '\n'; } } void print() { for (ll i = 1; i <= sz; i++) { cout << i << ": "; for (auto j : pos[i]) { cout << "{" << j << ": " << query(i, i, j, j) << "} "; } cout << '\n'; } } }; struct Operation { bool typ; // 0 = update, 1 = query ll x1, y1, x2, y2, t; pll val; Operation(ll _x1, ll _y1, pll _val) { typ = 0; x1 = _x1, y1 = _y1, val = _val; } Operation(ll _x1, ll _y1, ll _x2, ll _y2, ll _t) { typ = 1; x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2, t = _t; } }; int n, q; bool lamps[maxN]; set<pll> segments; vector<Operation> op; int main() { scanf("%d %d", &n, &q); char c; for (int i = 1; i <= n; i++) { scanf(" %c", &c); lamps[i] = (c == '1'); } FenwickTree2D values = FenwickTree2D(n); FenwickTree2D toggled = FenwickTree2D(n); // NOTE: because we need <= operator in lower_bound, // all set elements are negative for (int start = -1, i = 1; i <= n+1; i++) { if (lamps[i]) { if (start == -1) {start = i;} } else { if (start != -1) { segments.insert({-start, -(i-1)}); values.addPos(start, i-1); toggled.addPos(start, i-1); op.push_back(Operation(start, i-1, {q, 1})); start = -1; } } } char typ[10]; for (int a, b, i = 1; i <= q; i++) { scanf(" %s", typ); if (typ[0] == 't') { scanf("%d", &a); if (lamps[a]) { // toggle the lamp off // remove segment of current lamp auto cseg_it = segments.lower_bound({-a, -iINF}); pll cseg = *cseg_it; //cout << "cseg " << cseg.fi << ' ' << cseg.se << '\n'; segments.erase(cseg); values.addPos(-cseg.fi, -cseg.se); toggled.addPos(-cseg.fi, -cseg.se); op.push_back(Operation(-cseg.fi, -cseg.se, {-(q-i), -1})); // insert new segments (except if it's of length 0) // left segment if (a != -cseg.fi) { segments.insert({cseg.fi, -(a-1)}); values.addPos(-cseg.fi, a-1); toggled.addPos(-cseg.fi, a-1); op.push_back(Operation(-cseg.fi, a-1, {q-i, 1})); } // right segment if (a != -cseg.se) { segments.insert({-(a+1), cseg.se}); values.addPos(a+1, -cseg.se); toggled.addPos(a+1, -cseg.se); op.push_back(Operation(a+1, -cseg.se, {q-i, 1})); } } else { // toggle the lamp on pll newseg = {-a, -a}; // check if lamps next to it are on // left if (lamps[a-1]) { auto lseg_it = segments.lower_bound({-(a-1), -iINF}); pll lseg = *lseg_it; newseg.fi = lseg.fi; segments.erase(lseg); values.addPos(-lseg.fi, -lseg.se); toggled.addPos(-lseg.fi, -lseg.se); op.push_back(Operation(-lseg.fi, -lseg.se, {-(q-i), -1})); } // right if (lamps[a+1]) { auto rseg_it = segments.lower_bound({-(a+1), -iINF}); pll rseg = *rseg_it; newseg.se = rseg.se; segments.erase(rseg); values.addPos(-rseg.fi, -rseg.se); toggled.addPos(-rseg.fi, -rseg.se); op.push_back(Operation(-rseg.fi, -rseg.se, {-(q-i), -1})); } // insert new segment segments.insert(newseg); values.addPos(-newseg.fi, -newseg.se); toggled.addPos(-newseg.fi, -newseg.se); op.push_back(Operation(-newseg.fi, -newseg.se, {q-i, 1})); } lamps[a] = !lamps[a]; } else { scanf("%d %d", &a, &b); op.push_back(Operation(1, b-1, a, n, i)); } //for (auto i : segments) {cout << "{" << i.fi << ", " << i.se << "} ";} //cout << '\n'; //D.print(); //cout << '\n'; } values.build(); toggled.build(); //values.printPos(); //toggled.printPos(); for (auto O : op) { if (O.typ == 0) { //printf("Update %lld %lld with %lld %lld\n", O.x1, O.y1, O.val.fi, O.val.se); values.update(O.x1, O.y1, O.val.fi); toggled.update(O.x1, O.y1, O.val.se); //values.print(); //toggled.print(); } else { //printf("Query (%lld %lld) to (%lld %lld) at time %lld\n", O.x1, O.y1, O.x2, O.y2, O.t); ll v = values.query(O.x1, O.x2, O.y1, O.y2); ll t = toggled.query(O.x1, O.x2, O.y1, O.y2); //printf("%lld %lld\n", v, t); ll fin = v - (1ll * t * (q-O.t)); printf("%lld\n", fin); } } }

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

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~
street_lamps.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |   scanf(" %s", typ);
      |   ~~~~~^~~~~~~~~~~~
street_lamps.cpp:215:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |    scanf("%d", &a);
      |    ~~~~~^~~~~~~~~~
street_lamps.cpp:287:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |    scanf("%d %d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~
#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...