oj.uz

Submission #252407

# Submission time Handle Problem Language Result Execution time Memory
252407 2020-07-25T13:27:31 Z khangal Street Lamps (APIO19_street_lamps) C++14
40 / 100
 1147 ms 133268 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long , long long > pl;
const int N=1e6+1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18 
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,h,a[1234567],w,x,y,z;
ll c1[123][123];
bool used[1234567],used1[1234567];
pl p[1234567];
string s,s1[1234567];
map<ll,ll> mp;
map<pl,ll> mpl;
vector<pl> vec,vec1,ansvec;
vector<ll> v[1234567],v1[1234567];
vector<ll> vp[1234567];
set<ll> st;
stack <ll> sta;
int main(){
    cin>>n>>m;
    cin>>s;
    rep(i,0,n-1)if(s[i]=='1')d[i]=0;
    if(n<=100&&m<=100){
    rep(i,0,n-1)c1[0][i+1]=s[i]-'0';
    rep(k,1,m){
        string str;
        cin>>str;
        rep(i,1,n)c1[k][i]=c1[k-1][i];
        if(str == "query"){
            c[k]=1;
            cin>>x>>y;
            ans=0;
            rep(i,0,k-1){
                ll res=1;
                rep(j,x,y-1){
                    if(c1[i][j]==0)res=0;
                }
                ans += res;
            }
            cout<<ans<<'\n';
        }
        else{
            cin>>x;
            if(c1[k][x]==1)c1[k][x]=0;
            else c1[k][x]=1;
        }
    }}
    else{
        rep(k,1,m){
            string str;
            cin>>str;
            if(str=="query"){
                cin>>x>>y;
                x--;
                y--;
                if(s[x]=='1')c[x]+=(k - d[x]),d[x]=k;
                cout<<c[x]<<'\n';
            }
            else{
                cin>>x;
                x--;
                if(s[x]=='1'){
                    c[x] += (k - d[x]);
                    s[x]='0';
                }
                else s[x]='1',d[x]=k;
            }
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 126072 KB Output is correct
2 Correct 65 ms 126012 KB Output is correct
3 Correct 73 ms 126072 KB Output is correct
4 Correct 67 ms 126072 KB Output is correct
5 Correct 71 ms 126200 KB Output is correct
6 Correct 69 ms 126072 KB Output is correct
7 Correct 69 ms 126072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 127096 KB Output is correct
2 Correct 690 ms 126960 KB Output is correct
3 Correct 680 ms 127040 KB Output is correct
4 Correct 713 ms 131860 KB Output is correct
5 Correct 827 ms 132276 KB Output is correct
6 Correct 739 ms 131796 KB Output is correct
7 Correct 1147 ms 127124 KB Output is correct
8 Correct 1129 ms 133268 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 126072 KB Output is correct
2 Correct 65 ms 126012 KB Output is correct
3 Correct 73 ms 126072 KB Output is correct
4 Correct 67 ms 126072 KB Output is correct
5 Correct 71 ms 126200 KB Output is correct
6 Correct 69 ms 126072 KB Output is correct
7 Correct 69 ms 126072 KB Output is correct
8 Correct 610 ms 127096 KB Output is correct
9 Correct 690 ms 126960 KB Output is correct
10 Correct 680 ms 127040 KB Output is correct
11 Correct 713 ms 131860 KB Output is correct
12 Correct 827 ms 132276 KB Output is correct
13 Correct 739 ms 131796 KB Output is correct
14 Correct 1147 ms 127124 KB Output is correct
15 Correct 1129 ms 133268 KB Output is correct
16 Incorrect 65 ms 125944 KB Output isn't correct
17 Halted 0 ms 0 KB -