제출 #659013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659013		MohammadAghil	가로등 (APIO19_street_lamps)	C++17	100 / 100	3122 ms	177512 KiB

street_lamps

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     //      freopen("inp.txt", "r", stdin);
     //      freopen("out.txt", "w", stdout);
     // #else
     //      #define er(args ...) 0
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 3e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

vector<ll> fen[maxn], srt[maxn];

void upd(int x, int y, int k){
     for(x++; x < maxn; x += x&-x){
          for(int p = upper_bound(all(srt[x]), y) - begin(srt[x]); p <= sz(fen[x]); p += p&-p) fen[x][p-1] += k;
     }
}
ll get(int x, int y){
     ll res = 0;
     for(x++; x; x -= x&-x){
          for(int p = upper_bound(all(srt[x]), y) - begin(srt[x]); p; p -= p&-p) res += fen[x][p-1];
     }
     return res;
}
void addf(int x, int y){
     for(x++; x < maxn; x += x&-x) srt[x].pb(y);
}
void upd(int x1, int x2, int y1, int y2, int k, bool f = true){
     if(f){
          upd(x1, y1, k), upd(x2 + 1, y2 + 1, k);
          upd(x1, y2 + 1, -k), upd(x2 + 1, y1, -k);
     } else{
          addf(x1, y1), addf(x2 + 1, y2 + 1);
          addf(x1, y2 + 1), addf(x2 + 1, y1);
     }
}

set<int> em;
void add(int p, int t, bool f = true){
     em.erase(p);
     auto nxt = em.upper_bound(p), prv = prev(nxt);
     upd(*prv + 1, p, p, *nxt - 1, -t, f);
}
void rem(int p, int t, bool f = true){
     auto nxt = em.upper_bound(p), prv = prev(nxt);
     upd(*prv + 1, p, p, *nxt - 1, t, f);
     em.insert(p);
}
bool chk(int l, int r){
     auto it = em.lower_bound(l);
     return it == end(em) || *it > r;
}

int main(){ IOS();
     int n, q; cin >> n >> q;
     em.insert(-1), em.insert(n);
     vector<bool> cr(n), bs;
     rep(i,0,n){
          char c; cin >> c;
          if(c == '0') em.insert(i);
          else cr[i] = true;
     }
     bs = cr;
     vector<pp> query(q);
     rep(i,0,q){
          string t; cin >> t;
          if(t[0] == 'q'){
               int l, r; cin >> l >> r; l--, r -= 2;
               addf(l, r);
               query[i] = {l, r};
          } else{
               int l; cin >> l; l--;
               query[i] = {l, -1};
               if(cr[l]) rem(l, i + 1, false);
               else add(l, i + 1, false);
               cr[l] = !cr[l];
          }
     }
     rep(i,0,maxn){
          sort(all(srt[i])), srt[i].erase(unique(all(srt[i])), end(srt[i]));
          fen[i].resize(sz(srt[i]));
     }
     cr = bs;
     em.clear();
     em.insert(-1), em.insert(n);
     rep(i,0,n) if(!cr[i]) em.insert(i);
     rep(i,0,q){
          auto[l, r] = query[i];
          if(r == -1){
               if(cr[l]) rem(l, i + 1);
               else add(l, i + 1);
               cr[l] = !cr[l];
          }else{
               cout << get(l, r) + chk(l, r)*(i + 1) << '\n';
          }
     }
     return 0-0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20