oj.uz

Submission #983130

# Submission time Handle Problem Language Result Execution time Memory
983130 2024-05-15T08:35:42 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 134 ms 27108 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; 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'){
            a[x] = 1 - a[x];
            if(a[x] == 0)
                d[x] += j - b[x];
            b[x] = j;
        }
        if(0 && 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(0 && 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] == 't'){
                join(x , x + 1 , j);
            }else {
                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 1 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 55 ms 25572 KB Output is correct
6 Correct 74 ms 26356 KB Output is correct
7 Correct 82 ms 27108 KB Output is correct
8 Correct 134 ms 25284 KB Output is correct
9 Correct 62 ms 12116 KB Output is correct
10 Correct 69 ms 12384 KB Output is correct
11 Correct 70 ms 12624 KB Output is correct
12 Correct 96 ms 19688 KB Output is correct
13 Correct 117 ms 25060 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10716 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 1 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -