oj.uz

Submission #973230

# Submission time Handle Problem Language Result Execution time Memory
973230 2024-05-01T16:29:49 Z vjudge1 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2889 ms 311116 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=3e5+20, inf=1e18;

struct BIT2d{
   int n;
   vector<pair<int, pair<int, int>>> t[N];
   void init(int _n){
      n=_n;
      for (int i=1; i<=n; ++i) t[i].push_back({-1, {0, 0}});
   }
   void fake_update(int x, int y){
      for (int i=x; i<=n; i+=i&(-i)) t[i].push_back({y, {0, 0}});
   }
   void compress(){
      for (int i=1; i<=n; ++i){
         sort(t[i].begin(), t[i].end());
         t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
      }
   }
   void update(int x, int y, int t1, int t2){
      if (x>n || y>n) return;
      for (int i=x; i<=n; i+=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, make_pair(-inf, -inf)))-t[i].begin(); j<(int)t[i].size(); j+=j&(-j)){
            t[i][j].second.first+=t1;
            t[i][j].second.second+=t2;
         }
      }
   }
   pair<int, int> get(int x, int y){
      pair<int, int> ans={0, 0};
      for (int i=x; i; i-=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y+1, make_pair(-inf, -inf)))-t[i].begin()-1; j; j-=j&(-j)){
            ans.first+=t[i][j].second.first;
            ans.second+=t[i][j].second.second;
         }
      }
      return ans;
   }
};

struct Event{
   int lx, rx, ly, ry, idx;
   Event (int _lx=0, int _rx=0, int _ly=0, int _ry=0, int _idx=0){
      lx=_lx, rx=_rx, ly=_ly, ry=_ry, idx=_idx;
   }
   bool operator<(const Event &b){
      if (rx==b.rx) return idx<b.idx;
      return rx>b.rx;
   }
};

int n, q, ans[N], is_query[N];
string s;

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   vector<Event> v;
   set<pair<int, int>> st;
   map<pair<int, int>, int> mp;
   cin >> n >> q >> s;
   auto insert=[&](int t, int l, int r){
      mp[{l, r}]=t;
      st.emplace(l, r);
   };
   auto erase=[&](int tr, int l, int r){
      int tl=mp[{l, r}];
      v.emplace_back(l, r, tl, tr-1);
      st.erase({l, r});
      mp.erase({l, r});
   };
   s=" "+s;
   for (int i=1; i<=n; ++i) if (s[i]=='1'){
      int j=i;
      while (j<n && s[j+1]=='1') ++j;
      insert(1, i, j);
      i=j;
   }
   for (int i=2; i<=q+1; ++i){
      string type; cin >> type;
      if (type[0]=='t'){
         int x; cin >> x;
         if (s[x]=='0'){
            if (st.empty()){
               insert(i, x, x);
            }else{
               auto it=st.lower_bound({x, x});
               int l=x, r=x;
               if (it!=st.end() && x+1==it->first){
                  r=it->second;
                  erase(i, it->first, it->second);
                  it=st.lower_bound({x, x});
               }
               if (it!=st.begin() && (--it)->second==l-1){
                  l=it->first;
                  erase(i, it->first, it->second);
               }
               insert(i, l, r);
            }
         }else{
            auto it=st.lower_bound({x, (int)1e9}); --it;
            int l=it->first, r=it->second;
            erase(i, l, r);
            if (l!=x) insert(i, l, x-1);
            if (r!=x) insert(i, x+1, r);
         }
         s[x]^=1;
      }else{
         is_query[i]=1;
         int l, r; cin >> l >> r; --r;
         v.emplace_back(l, r, 1, i-1, i);
      }
   }
   vector<pair<int, int>> tmp(st.begin(), st.end());
   for (auto &i:tmp) erase(q+2, i.first, i.second);
   sort(v.begin(), v.end());
   BIT2d bit;
   bit.init(N-1);
   for (auto &i:v){
      if (i.idx==0){
         bit.fake_update(i.lx, i.ly);
         bit.fake_update(i.lx, i.ry);
      }
   }
   bit.compress();
   for (auto &i:v){
      if (i.idx==0){
         // cout << "update " << i.lx << ' ' << i.ly << ' ' << 1 << ' ' << -i.ly+1 << '\n';
         // cout << "update " << i.lx << ' ' << i.ry << ' ' << -1 << ' ' << i.ry << '\n';
         bit.update(i.lx, i.ly, 1, -i.ly+1);
         bit.update(i.lx, i.ry, -1, i.ry);
      }else{
         // cout << "query " << i.lx << ' ' << i.ry << '\n';
         auto tmp=bit.get(i.lx, i.ry);
         ans[i.idx]=tmp.first*i.ry+tmp.second;
      }
   }
   for (int i=2; i<=q+1; ++i) if (is_query[i]) cout << ans[i] << '\n';
   return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 18780 KB Output is correct
2 Correct 22 ms 18780 KB Output is correct
3 Correct 22 ms 18780 KB Output is correct
4 Correct 22 ms 19036 KB Output is correct
5 Correct 22 ms 19052 KB Output is correct
6 Correct 20 ms 18780 KB Output is correct
7 Correct 19 ms 18780 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1521 ms 207188 KB Output is correct
2 Correct 1559 ms 188248 KB Output is correct
3 Correct 1403 ms 158596 KB Output is correct
4 Correct 1103 ms 179808 KB Output is correct
5 Correct 1070 ms 163556 KB Output is correct
6 Correct 1132 ms 193636 KB Output is correct
7 Correct 132 ms 41244 KB Output is correct
8 Correct 137 ms 42896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 20048 KB Output is correct
2 Correct 26 ms 19544 KB Output is correct
3 Correct 25 ms 19540 KB Output is correct
4 Correct 20 ms 18792 KB Output is correct
5 Correct 1536 ms 230416 KB Output is correct
6 Correct 1548 ms 197048 KB Output is correct
7 Correct 1285 ms 164376 KB Output is correct
8 Correct 161 ms 42008 KB Output is correct
9 Correct 104 ms 34484 KB Output is correct
10 Correct 120 ms 37240 KB Output is correct
11 Correct 115 ms 37800 KB Output is correct
12 Correct 154 ms 41148 KB Output is correct
13 Correct 166 ms 42524 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19292 KB Output is correct
2 Correct 24 ms 19548 KB Output is correct
3 Correct 25 ms 19700 KB Output is correct
4 Correct 26 ms 20048 KB Output is correct
5 Correct 451 ms 108192 KB Output is correct
6 Correct 865 ms 161196 KB Output is correct
7 Correct 1228 ms 191992 KB Output is correct
8 Correct 1715 ms 271540 KB Output is correct
9 Correct 2124 ms 240984 KB Output is correct
10 Correct 2889 ms 310756 KB Output is correct
11 Correct 2132 ms 237444 KB Output is correct
12 Correct 2853 ms 308856 KB Output is correct
13 Correct 2121 ms 236636 KB Output is correct
14 Correct 2846 ms 311116 KB Output is correct
15 Correct 168 ms 41696 KB Output is correct
16 Correct 198 ms 43560 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 18780 KB Output is correct
2 Correct 22 ms 18780 KB Output is correct
3 Correct 22 ms 18780 KB Output is correct
4 Correct 22 ms 19036 KB Output is correct
5 Correct 22 ms 19052 KB Output is correct
6 Correct 20 ms 18780 KB Output is correct
7 Correct 19 ms 18780 KB Output is correct
8 Correct 1521 ms 207188 KB Output is correct
9 Correct 1559 ms 188248 KB Output is correct
10 Correct 1403 ms 158596 KB Output is correct
11 Correct 1103 ms 179808 KB Output is correct
12 Correct 1070 ms 163556 KB Output is correct
13 Correct 1132 ms 193636 KB Output is correct
14 Correct 132 ms 41244 KB Output is correct
15 Correct 137 ms 42896 KB Output is correct
16 Correct 25 ms 20048 KB Output is correct
17 Correct 26 ms 19544 KB Output is correct
18 Correct 25 ms 19540 KB Output is correct
19 Correct 20 ms 18792 KB Output is correct
20 Correct 1536 ms 230416 KB Output is correct
21 Correct 1548 ms 197048 KB Output is correct
22 Correct 1285 ms 164376 KB Output is correct
23 Correct 161 ms 42008 KB Output is correct
24 Correct 104 ms 34484 KB Output is correct
25 Correct 120 ms 37240 KB Output is correct
26 Correct 115 ms 37800 KB Output is correct
27 Correct 154 ms 41148 KB Output is correct
28 Correct 166 ms 42524 KB Output is correct
29 Correct 22 ms 19292 KB Output is correct
30 Correct 24 ms 19548 KB Output is correct
31 Correct 25 ms 19700 KB Output is correct
32 Correct 26 ms 20048 KB Output is correct
33 Correct 451 ms 108192 KB Output is correct
34 Correct 865 ms 161196 KB Output is correct
35 Correct 1228 ms 191992 KB Output is correct
36 Correct 1715 ms 271540 KB Output is correct
37 Correct 2124 ms 240984 KB Output is correct
38 Correct 2889 ms 310756 KB Output is correct
39 Correct 2132 ms 237444 KB Output is correct
40 Correct 2853 ms 308856 KB Output is correct
41 Correct 2121 ms 236636 KB Output is correct
42 Correct 2846 ms 311116 KB Output is correct
43 Correct 168 ms 41696 KB Output is correct
44 Correct 198 ms 43560 KB Output is correct
45 Correct 773 ms 145840 KB Output is correct
46 Correct 1031 ms 127456 KB Output is correct
47 Correct 826 ms 117936 KB Output is correct
48 Correct 1357 ms 178944 KB Output is correct
49 Correct 136 ms 38564 KB Output is correct
50 Correct 123 ms 38880 KB Output is correct
51 Correct 135 ms 39696 KB Output is correct
52 Correct 121 ms 39084 KB Output is correct
53 Correct 127 ms 38600 KB Output is correct
54 Correct 119 ms 37804 KB Output is correct