oj.uz

답안 #401891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401891 2021-05-11T00:27:15 Z kai824 가로등 (APIO19_street_lamps) C++17
40 / 100
 5000 ms 472508 KB 
#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define eb emplace_back
#define mp make_pair
typedef pair<int,int> pii;
#define f first
#define s second
 
#ifdef local
#define debug(x,label) cerr<<"DEBUG "<<label<<" "<<x<<'\n';
#else
#define debug(x,label);
#endif
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef cc_hash_table<int, int, hash<int>> ht;
 
//const int mod=1000000007 or 998244353;
 
int n,q;
ht ft[300005];
#define ls(x) (x&(-x))
void update(int a,int b,int upd){b++;
  //cout<<a<<' '<<b<<' '<<upd<<" UPDATE\n";
  for(;a<=n;a+=ls(a)){
    for(int x=b;x<=n;x+=ls(x)){
      if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
      else ft[a][x]+=upd;
    }
  }
}
int query(int a,int b){b++;
  int ans=0;
  for(;a;a-=ls(a)){
    for(int x=b;x;x-=ls(x)){
      //if(ft[a].find(x)==ft[a].end())continue;
      ans+=ft[a][x];
    }
  }
  return ans;
}
 
bool lam[300005];
 
int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int prev=0,ans,a,b,c,d;
  cin>>n>>q;
  string s;
  cin>>s;
  set<pair<pii,int> > cur;//"cur ranges"
  set<pair<pii,int> >::iterator it;
  for(int i=0;i<n;i++){
    if(s[i]=='0'){
      if(prev<=i-1){
        cur.insert(mp(mp(prev+1,i),0));
      }
      prev=i+1;
    }
    lam[i+1]=(s[i]=='1');
  }
  if(prev<=n-1){
    cur.insert(mp(mp(prev+1,n),0));
  }
 
  for(int i=1;i<=q;i++){
    cin>>s;
    if(s[0]=='t'){
      cin>>a;
      if(lam[a]){
        it=--cur.upper_bound(mp(mp(a,INT_MAX),-1));
        b=it->f.f;c=it->f.s;//range b to c...
        update(b,n-c,i-it->s);
        cur.erase(it);
        if(b<a)cur.insert(mp(mp(b,a-1),i));
        if(a<c)cur.insert(mp(mp(a+1,c),i));
      }else{
        b=c=a;
        if(lam[a-1]){
          it=--cur.upper_bound(mp(mp(a-1,INT_MAX),-1));
          b=it->f.f;
          update(it->f.f,n-it->f.s,i-it->s);
          cur.erase(it);
        }
        if(lam[a+1]){
          it=--cur.upper_bound(mp(mp(a+1,INT_MAX),-1));
          c=it->f.s;
          update(it->f.f,n-it->f.s,i-it->s);
          cur.erase(it);
        }
        cur.insert(mp(mp(b,c),i));
      }
      lam[a]^=1;
    }else{
      ans=0;
      cin>>a>>b;b--;
      it=cur.upper_bound(mp(mp(a,INT_MAX),-1));
      if(it!=cur.begin()){
        it--;
        if(it->f.f<=a && b<=it->f.s){
          ans+=(i-it->s);
        }
      }
      ans+=query(a,n-b);//if first index >=a, then n-first index<=n-a
      cout<<ans<<'\n';
    }
  }
  return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:54:24: warning: unused variable 'd' [-Wunused-variable]
   54 |   int prev=0,ans,a,b,c,d;
      |                        ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 54200 KB Output is correct
2 Correct 59 ms 54304 KB Output is correct
3 Correct 60 ms 54248 KB Output is correct
4 Correct 60 ms 54340 KB Output is correct
5 Correct 62 ms 54212 KB Output is correct
6 Correct 60 ms 54260 KB Output is correct
7 Correct 60 ms 54340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 55364 KB Output is correct
2 Correct 260 ms 55560 KB Output is correct
3 Correct 549 ms 62544 KB Output is correct
4 Correct 4444 ms 366628 KB Output is correct
5 Correct 4882 ms 389408 KB Output is correct
6 Correct 4059 ms 368920 KB Output is correct
7 Correct 2434 ms 253392 KB Output is correct
8 Correct 2452 ms 255612 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 54680 KB Output is correct
2 Correct 66 ms 54840 KB Output is correct
3 Correct 68 ms 55060 KB Output is correct
4 Correct 69 ms 54880 KB Output is correct
5 Correct 4227 ms 288192 KB Output is correct
6 Execution timed out 5085 ms 404116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 54980 KB Output is correct
2 Correct 67 ms 55000 KB Output is correct
3 Correct 69 ms 54828 KB Output is correct
4 Correct 66 ms 54612 KB Output is correct
5 Execution timed out 5048 ms 472508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 54200 KB Output is correct
2 Correct 59 ms 54304 KB Output is correct
3 Correct 60 ms 54248 KB Output is correct
4 Correct 60 ms 54340 KB Output is correct
5 Correct 62 ms 54212 KB Output is correct
6 Correct 60 ms 54260 KB Output is correct
7 Correct 60 ms 54340 KB Output is correct
8 Correct 209 ms 55364 KB Output is correct
9 Correct 260 ms 55560 KB Output is correct
10 Correct 549 ms 62544 KB Output is correct
11 Correct 4444 ms 366628 KB Output is correct
12 Correct 4882 ms 389408 KB Output is correct
13 Correct 4059 ms 368920 KB Output is correct
14 Correct 2434 ms 253392 KB Output is correct
15 Correct 2452 ms 255612 KB Output is correct
16 Correct 66 ms 54680 KB Output is correct
17 Correct 66 ms 54840 KB Output is correct
18 Correct 68 ms 55060 KB Output is correct
19 Correct 69 ms 54880 KB Output is correct
20 Correct 4227 ms 288192 KB Output is correct
21 Execution timed out 5085 ms 404116 KB Time limit exceeded
22 Halted 0 ms 0 KB -