oj.uz

Submission #386765

# Submission time Handle Problem Language Result Execution time Memory
386765 2021-04-07T09:32:36 Z clifter Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 67168 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];
ll fw1[300500], fw2[300500];
set<int> S;
event EA[300500][4],EB[1005000];
int Asize[300500];
vector<event> EA0;

ll sum(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) return;

  cdq(l, mid, n);
  cdq(mid+1, r, n);

  int EBS = 0;

  for(int i=l; i<=r; i++){

    if(i==0) {
      for(int j=0; j<EA0.size(); j++){
        EB[EBS++] = EA0[j];
      }
    }

    else{
      for(int j=0; j<Asize[i]; j++){
        EB[EBS++] = EA[i][j];
      }
    }

  }

  sort(EB, EB+EBS, cmpx);

  for(int i=0; i<=n+1; i++) {fw1[i] = 0; fw2[i] = 0;}
  for(int i=0; i<EBS; i++){

    if(EB[i].t<=mid){

      int x = n+2-EB[i].y;
      while(x < n+2) {
        fw1[x] += EB[i].value*EB[i].t;
        fw2[x] += EB[i].value;
        x += (x & -x);
      }

    }

    if(EB[i].t>mid) {
      
      int x = n+2-EB[i].y;
      while (x > 0) {

        ans[EB[i].t] += fw2[x]*EB[i].t;
        ans[EB[i].t] -= fw1[x];
        x -= (x & -x);

      }
    }
  }

}

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++){

    if(last[i]==i){

      event e = {0, first[i], i, 1};
      EA0.push_back(e);

    }
  }

  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][Asize[i]++] = e;
      toggle[i] = 1;

    }
    else{

      int a;
      event e1, e2, e3;
      cin>>a;
      if(s[a-1]=='0'){

        s[a-1]='1';

        e1 = {i, a+1, last[a+1], -1};
        e2 = {i, first[a], last[a+1], 1};
        e3 = {i, first[a], a, -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];

        e1 = {i, x1, x2, -1};
        e2 = {i, x1, a, 1};
        e3 = {i, a+1, x2, 1};


        last[x1] = a;
        last[a+1] = x2;
        first[a] = x1;
        first[x2] = a+1;
        S.insert(a);

      }

      EA[i][Asize[i]++] = e1;
      EA[i][Asize[i]++] = e2;
      EA[i][Asize[i]++] = e3;
    
    }
  }

  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 cdq(int, int, int)':
street_lamps.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       for(int j=0; j<EA0.size(); j++){
      |                    ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1639 ms 48620 KB Output is correct
2 Correct 1759 ms 48436 KB Output is correct
3 Correct 3076 ms 48784 KB Output is correct
4 Execution timed out 5013 ms 53552 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 748 KB Output is correct
2 Correct 6 ms 748 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Execution timed out 5101 ms 67168 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 6 ms 620 KB Output is correct
5 Execution timed out 5033 ms 53132 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1639 ms 48620 KB Output is correct
9 Correct 1759 ms 48436 KB Output is correct
10 Correct 3076 ms 48784 KB Output is correct
11 Execution timed out 5013 ms 53552 KB Time limit exceeded
12 Halted 0 ms 0 KB -