oj.uz

Submission #440525

# Submission time Handle Problem Language Result Execution time Memory
440525 2021-07-02T11:21:24 Z den_tar Street Lamps (APIO19_street_lamps) C++14
40 / 100
 841 ms 22496 KB 
#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio();cin.tie();cout.tie();
#define en cout<<endl;
#define ops cout<<"ops"<<endl;
#define line cout<<"---------------------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pllll;
typedef string str;

const ll DIM = 3e5 + 7;
const ll DIMM = 5e4 + 7;
const ll DDIM = 7;
const ll INF = 1e18 + 7;
const ll X = 1e5 + 7;
const ll BS = 2e5 + 7;
const ll AS = 26 + 7;
const ll MODULO = 1e9 + 7;

ll nt,n,m,k,q;

str s,type[DIM];

ll v1[DIM],v2[DIM];

ll a[DIM],b[DIM],last[DIM];

ll cres;

bool f;

bool check(ll p1,ll p2){

    for(int i=p1;i<p2;i++)
     if(b[i]==0)return false;

    return true;
}

void solve1(){
     for(int i=0;i<n;i++)a[i+1]=s[i]-'0';

     for(int qq=1;qq<=q;qq++){

     cin>>type[qq]>>v1[qq];


     if(type[qq]=="query"){

      cin>>v2[qq];

      cres=0;

      for(int i=1;i<=n;i++)b[i]=a[i];

      f=check(v1[qq],v2[qq]);

      if(f)cres++;

      for(int j=1;j<qq;j++){

       if(type[j]=="toggle"){

        b[v1[j]]=1-b[v1[j]];

        f=check(v1[qq],v2[qq]);
       }

       if(f)cres++;

      }

      cout<<cres<<endl;

     }

    }
}

void solve2(){

     for(int i=0;i<n;i++)a[i+1]=s[i]-'0';

     for(int qq=1;qq<=q;qq++){

     cin>>type[qq]>>v1[qq];

     if(type[qq]=="toggle"){

      a[v1[qq]]=1-a[v1[qq]];

      if(a[v1[qq]]==1)last[v1[qq]]=qq;
      else b[v1[qq]]+=qq-last[v1[qq]];
     }
     else{
      cin>>v2[qq];

      cres=b[v1[qq]];

      if(a[v1[qq]]==1)cres+=qq-last[v1[qq]];

      cout<<cres<<endl;
     }

    }
}

int main()
{
    fast;
    //ll x1,y1,x2,y2;

    cin>>n>>q>>s;

    if(n<=100 && q<=100){
     solve1();
     return 0;
    }

    solve2();

    return 0;
}

/*

5 7
10110
query 1 2
query 1 2
toggle 2
query 2 3
query 3 4
query 5 6
query 2 3

*/

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 15216 KB Output is correct
2 Correct 449 ms 15300 KB Output is correct
3 Correct 481 ms 15576 KB Output is correct
4 Correct 553 ms 22496 KB Output is correct
5 Correct 621 ms 20484 KB Output is correct
6 Correct 499 ms 21048 KB Output is correct
7 Correct 829 ms 17704 KB Output is correct
8 Correct 841 ms 19108 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 9716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9696 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 456 ms 15216 KB Output is correct
9 Correct 449 ms 15300 KB Output is correct
10 Correct 481 ms 15576 KB Output is correct
11 Correct 553 ms 22496 KB Output is correct
12 Correct 621 ms 20484 KB Output is correct
13 Correct 499 ms 21048 KB Output is correct
14 Correct 829 ms 17704 KB Output is correct
15 Correct 841 ms 19108 KB Output is correct
16 Incorrect 6 ms 9676 KB Output isn't correct
17 Halted 0 ms 0 KB -