oj.uz

Submission #983138

# Submission time Handle Problem Language Result Execution time Memory
983138 2024-05-15T08:39:52 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 131 ms 23304 KB 
#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

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.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9592 KB Output is correct
2 Correct 56 ms 7560 KB Output is correct
3 Correct 59 ms 7620 KB Output is correct
4 Correct 90 ms 22996 KB Output is correct
5 Correct 96 ms 22324 KB Output is correct
6 Correct 92 ms 23304 KB Output is correct
7 Correct 73 ms 13700 KB Output is correct
8 Correct 92 ms 19324 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 61 ms 21488 KB Output is correct
6 Correct 74 ms 21596 KB Output is correct
7 Correct 88 ms 21732 KB Output is correct
8 Correct 124 ms 19360 KB Output is correct
9 Correct 64 ms 7460 KB Output is correct
10 Correct 85 ms 7432 KB Output is correct
11 Correct 67 ms 7508 KB Output is correct
12 Correct 76 ms 13696 KB Output is correct
13 Correct 131 ms 19252 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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