제출 #1257989

#제출 시각아이디문제언어결과실행 시간메모리
1257989M_SH_OStreet Lamps (APIO19_street_lamps)C++20
0 / 100
5094 ms22748 KiB
#include <bits/stdc++.h> //#include "rainbow.h" #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> //#define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front #define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; const ll INF = 1e18; const int lg = 20; mt19937 rng(time(0)); ll randll(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } ll n; vll bit; void add(int i, ll val) { for (; i <= n; i += i & -i) bit[i] += val; } ll sum(int i) { ll res = 0; for (; i > 0; i -= i & -i) res += bit[i]; return res; } ll range_sum(int l, int r) { return sum(r+1) - sum(l); } int main(){ speed; ll q; cin >> n >> q; ll baze = sqrt(q); str s; cin >> s; set<pll> v; ll l = -1; for(int i = 0; i < n; i ++){ if(s[i] == '1'){ if(l == -1) l = i; } else{ if(l != -1){ v.insert({l, i-1}); l = -1; } } } if(l != -1) v.insert({l, n-1}); map<pll, ll> m; vll p(n+7, -1); vector<pair<pll, ll>> vi, qr; vll res(q, 0); vll p_; for(int i = 0; i < q; i ++){ if((i+1) % baze == 0){ sort(qr); bit.clear(); bit.resize(n+7, 0); ll l = 0; for(auto j : m){ while(l < qr.size() && qr[l].fr.fr < j.fr.fr){ res[qr[l].se] += range_sum(qr[l].fr.se, n-1); l++; } add(j.fr.se, j.se); } for(auto j : vi){ m[j.fr] += j.se; } qr.clear(); vi.clear(); } str s1; cin >> s1; if(s1 == "toggle"){ ll x; cin >> x; x --; if(s[x] == '0'){ ll l = x, r = x; if(v.size() && v.lower_bound({x, -1}) != v.begin() && (*--v.lower_bound({x, -1})).se == x-1){ pll p1 = *--v.lower_bound({x, -1}); v.erase(p1); vi.pb({p1, i-p[p1.fr]}); l = p1.fr; } if(v.lower_bound({x, -1}) != v.end() && (*v.lower_bound({x, -1})).fr == x+1){ pll p1 = *v.lower_bound({x, -1}); v.erase(p1); vi.pb({p1, i-p[p1.fr]}); r = p1.se; } p[l] = i; v.insert({l, r}); s[x] = '1'; } else{ pll p1 = *--v.upper_bound({x, INF}); v.erase(p1); vi.pb({p1, i-p[p1.fr]}); if(p1.fr != x){ p[p1.fr] = i; v.insert({p1.fr, x-1}); } if(p1.se != x){ p[x+1] = i; v.insert({x+1, p1.se}); } s[x] = '0'; } } else{ /*bit.clear(); bit.resize(n+7, 0);*/ p_.pb(i); ll l, r; cin >> l >> r; l --, r -= 2; qr.pb({{l, r}, i}); for(auto j : vi){ if(j.fr.fr <= l && r <= j.fr.se) res[i] += j.se; } if(v.upper_bound({l, INF}) != v.begin() && v.size()){ pll p1 = *--v.upper_bound({l, INF}); if(p1.se >= r) res[i] += i-p[p1.fr]; } } } sort(qr); bit.clear(); bit.resize(n+7, 0); l = 0; for(auto j : m){ while(l < qr.size() && qr[l].fr.fr < j.fr.fr){ res[qr[l].se] += range_sum(qr[l].fr.se, n-1); l++; } add(j.fr.se, j.se); } for(int i : p_){ cout << res[i] << endl; } }
#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...