oj.uz

Submission #386739

# Submission time Handle Problem Language Result Execution time Memory
386739 2021-04-07T08:56:57 Z clifter Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 210224 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#define ll long long
 
using namespace std;
class event{
 
  public:
    int t; int x; int y; ll value;
 
};
bool cmpt(event a, event b){return a.t<b.t;}
bool cmpx(event a, event b){if(a.x!=b.x) return a.x<b.x; else return a.t<b.t;}
 
int last[300500],first[300500],toggle[300500];
ll ans[300500], fw1[1005000], fw2[1005000];
set<int> S;
vector<event> EA[300500], ER;
void insert(vector<ll> &tree, int i, ll val){
 
  while(i < tree.size()) {
    tree[i] += val;
    i += (i & -i);
  }
}
ll sum(vector<ll> &tree, int i){
 
  ll ans = 0;
  while (i > 0) {
      ans += tree[i];
      i -= (i & -i);
  }
  return ans;
}
void cdq(int l, int r, int n){
 
  int mid = (l+r)/2;
  if(l==r) {
    
    ER.clear();
    sort(EA[l].begin(), EA[l].end(), cmpx);
    for(int i=0; i<EA[l].size(); i++) ER.push_back(EA[l][i]);
    return;
    
  }

  vector<event> EB, EC;
 
  cdq(l, mid, n);
  for(int i=0; i<ER.size(); i++) EC.push_back(ER[i]);
  cdq(mid+1, r, n);
 
  int pt1 = 0, pt2 = 0;
  while(pt1<EC.size()&&pt2<ER.size()){
    if(cmpx(EC[pt1], ER[pt2])) {EB.push_back(EC[pt1]); pt1++;}
    else {EB.push_back(ER[pt2]); pt2++;}
  }
  for(int i=pt1; i<EC.size(); i++) EB.push_back(EC[i]);
  for(int i=pt2; i<ER.size(); i++) EB.push_back(ER[i]);
 
  for(int i=0; i<=n+1; i++) {fw1[i] = 0; fw2[i] = 0;}
  for(int i=0; i<EB.size(); i++){
 
    if(EB[i].t<=mid){
 
      int x = EB[i].y;
      while(x < n+2) {
        fw1[x] += EB[i].value;
        fw2[x] += (EB[i].value>0)?1:((EB[i].value<0)?-1:0);
        x += (x & -x);
      }
 
    }
 
    if(EB[i].t>mid) {
      
      int x = EB[i].y;
      while (x > 0) {
        ans[EB[i].t] += fw2[x]*(EB[i].t+1);
        ans[EB[i].t] -= fw1[x];
        x -= (x & -x);
      }
 
    }
 
  }

  ER.clear();
  for(int i=0; i<EB.size(); i++) ER.push_back(EB[i]);

}
 
int main() {
 
 
  cin.sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
 
  int n, m;
  cin>>n>>m;
 
  string s;
  cin>>s;
 
 
  last[n+1] = n+1;
  first[1] = 1;
  for(int i=n+1; i>=2; i--) last[i-1] = (s[i-2]=='1')?last[i]:(i-1);
  for(int i=2; i<=n+1; i++) first[i] = (s[i-2]=='1')?first[i-1]:i;
  S.insert(n+1);
  for(int i=1; i<=n; i++) if(s[i-1]=='0') S.insert(i); 
 
  for(int i=1; i<=n+1; i++){
 
    event e[5];
    
    e[1] = {0, i,i,1};
    e[2] = {0, i,last[i]+1,-1};
    e[3] = {0, i+1,i,-1};
    e[4] = {0, i+1,last[i]+1, 1};
 
    for(int j=1; j<=4; j++)   EA[0].push_back(e[j]);
    
  }
 
  for(int i=1; i<=m; i++){
 
    string v;
    cin>>v;
 
    if(v=="query"){
 
      int x, y;
      cin>>x>>y;
      event e = {i, x, y, 0};
      EA[i].push_back(e);
      toggle[i] = 1;
 
    }
    else{
 
      int a;
      event e[5];
      cin>>a;
      if(s[a-1]=='0'){
 
        s[a-1]='1';
        e[1] = {i, first[a], a+1, i+1};
        e[2] = {i, first[a], last[a+1]+1, -(i+1)};
        e[3] = {i, a+1, a+1, -(i+1)};
        e[4] = {i, a+1, last[a+1]+1, i+1};
        last[first[a]] = last[a+1];
        first[last[a+1]] = first[a];
        auto k = S.find(a);
        S.erase(k);
 
      }
      else{
 
        s[a-1] = '0';
        int x1, x2;
        x2 = *S.lower_bound(a+1);
        x1 = first[x2];
        e[1] = {i, x1, a+1, -(i+1)};
        e[2] = {i, x1, x2+1, i+1};
        e[3] = {i, a+1, a+1, i+1};
        e[4] = {i, a+1, x2+1, -(i+1)};
        last[x1] = a;
        last[a+1] = x2;
        first[a] = x1;
        first[x2] = a+1;
        S.insert(a);
 
      }
 
      for(int j=1; j<=4; j++)  EA[i].push_back(e[j]);
   
    }
  }
 
  cdq(0, m, n);
  for(int i=1; i<=m; i++){
 
    if(toggle[i]==1) cout<<ans[i]<<"\n";
 
  }
  
  
}

Compilation message

street_lamps.cpp: In function 'void insert(std::vector<long long int>&, int, long long int)':
street_lamps.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   while(i < tree.size()) {
      |         ~~^~~~~~~~~~~~~
street_lamps.cpp: In function 'void cdq(int, int, int)':
street_lamps.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0; i<EA[l].size(); i++) ER.push_back(EA[l][i]);
      |                  ~^~~~~~~~~~~~~
street_lamps.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0; i<ER.size(); i++) EC.push_back(ER[i]);
      |                ~^~~~~~~~~~
street_lamps.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   while(pt1<EC.size()&&pt2<ER.size()){
      |         ~~~^~~~~~~~~~
street_lamps.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   while(pt1<EC.size()&&pt2<ER.size()){
      |                        ~~~^~~~~~~~~~
street_lamps.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i=pt1; i<EC.size(); i++) EB.push_back(EC[i]);
      |                  ~^~~~~~~~~~
street_lamps.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i=pt2; i<ER.size(); i++) EB.push_back(ER[i]);
      |                  ~^~~~~~~~~~
street_lamps.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0; i<EB.size(); i++){
      |                ~^~~~~~~~~~
street_lamps.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i=0; i<EB.size(); i++) ER.push_back(EB[i]);
      |                ~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 6 ms 7532 KB Output is correct
4 Correct 6 ms 7532 KB Output is correct
5 Correct 6 ms 7532 KB Output is correct
6 Correct 6 ms 7532 KB Output is correct
7 Correct 6 ms 7532 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 110592 KB Output is correct
2 Correct 863 ms 110584 KB Output is correct
3 Correct 2459 ms 112188 KB Output is correct
4 Execution timed out 5046 ms 203048 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8436 KB Output is correct
2 Correct 11 ms 8328 KB Output is correct
3 Correct 13 ms 8280 KB Output is correct
4 Correct 10 ms 8180 KB Output is correct
5 Execution timed out 5102 ms 210224 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8236 KB Output is correct
2 Correct 11 ms 8304 KB Output is correct
3 Correct 12 ms 8360 KB Output is correct
4 Correct 12 ms 8448 KB Output is correct
5 Execution timed out 5087 ms 191732 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 6 ms 7532 KB Output is correct
4 Correct 6 ms 7532 KB Output is correct
5 Correct 6 ms 7532 KB Output is correct
6 Correct 6 ms 7532 KB Output is correct
7 Correct 6 ms 7532 KB Output is correct
8 Correct 787 ms 110592 KB Output is correct
9 Correct 863 ms 110584 KB Output is correct
10 Correct 2459 ms 112188 KB Output is correct
11 Execution timed out 5046 ms 203048 KB Time limit exceeded
12 Halted 0 ms 0 KB -