Submission #983138

#	Time	Username	Problem	Language	Result	Execution time	Memory
983138		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	131 ms	23304 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N] ,  p[N] , sz[N] ,  d[N] , t[N];
ll  c[109][109];


ll get(int x){
    return (p[x] == x ? x : get(p[x]));
}
ll get1(int x , vector<pair<int,int>>&v){
    v.pb({x , t[x]});
    return (p[x] == x ? x : get1(p[x] , v));
}
void join(int x , int y , int k){
    x = get(x) , y = get(y);
    if(x != y){
        if(sz[x] < sz[y])
        swap(x , y);
        p[y] = x;
        sz[x] += sz[y];
        t[y] = k;
    }
}

void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
    cin>>n>>q;
    string str;
    cin>>str;
    set<pair<int,pair<int,int>>>st;
    for(i = 1; i <= n + 1; i++)
        p[i] = i , sz[i] = 1;
    for(i = 1; i <= n; i++){
        a[i] = str[i - 1] - '0';
        if(n <= 100)
            c[0][i] = c[0][i - 1] + (a[i] == 0) ;
        if(a[i] == 1)
            join(i , i + 1 , 0);
    }
    for(j = 1; j <= q;j ++){
        cin>>str>>x;
        if(str[0] == 'q')
            cin>>y;
        if(str[0] == 't'){
            join(x , x + 1 , j);
            a[x] = 1 - a[x];
            if(a[x] == 0)
                d[x] += j - b[x];
            b[x] = j;
        }
        if(max(n , q) <= 100){
            if(str[0] == 't')
                a[x] = 1 - a[x];
            for(i = 1; i <= n; i++)
                c[j][i] = c[j][i - 1] + (a[i] == 0);
            if(str[0] == 'q'){
                s = 0;
                for(i = 0; i < j; i++)
                    s += ((c[i][y - 1] - c[i][x - 1]) == 0);
                cout<<s<<"\n";
            }
        }else if( x == y - 1){
            if(str[0] == 'q'){
                s = d[x];
                if(a[x] == 1)
                    s += j - b[x];
                cout<<s<<"\n";
            }
        }else {
            if(str[0] == 'q'){
                if(get(x) != get(y)){
                    cout<<0<<"\n";
                }else {
                    vector<pair<int,int>>v1 = {{-1 , 0}} , v2 = {{0 , 0}};
                    get1(x , v1);
                    get1(y , v2);
                    l = v1.size() - 1 , r = v2.size() - 1;
                    x = 0;
                    while(true){
                        if(min(l , r) == 0 || (v1[l - 1].fi != v2[r - 1].fi)){
                            x = max(v1[l- 1].se , v2[r - 1].se);
                            break;
                        }
                        l-- , r--;
                    }
                    cout<<j - x<<"\n";
                }
            }
        }
    }
}

int main(){
    TL;

    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
//   cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message (stderr)

street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:46:46: warning: unused variable 'f' [-Wunused-variable]
   46 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                              ^
street_lamps.cpp:46:50: warning: unused variable 'k' [-Wunused-variable]
   46 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                  ^
street_lamps.cpp:46:54: warning: unused variable 'm' [-Wunused-variable]
   46 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                      ^
street_lamps.cpp:46:58: warning: unused variable 'mx' [-Wunused-variable]
   46 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                          ^~
street_lamps.cpp:46:67: warning: unused variable 'mn' [-Wunused-variable]
   46 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                                   ^~

• Subtask 1: 0 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20