oj.uz

Submission #983159

# Submission time Handle Problem Language Result Execution time Memory
983159 2024-05-15T08:49:49 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 153 ms 28368 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(y - x == 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 10588 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 57 ms 12744 KB Output is correct
2 Correct 56 ms 10960 KB Output is correct
3 Correct 58 ms 11604 KB Output is correct
4 Correct 87 ms 28216 KB Output is correct
5 Correct 91 ms 27692 KB Output is correct
6 Correct 110 ms 28368 KB Output is correct
7 Correct 91 ms 19736 KB Output is correct
8 Correct 108 ms 25104 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8548 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 57 ms 25704 KB Output is correct
6 Correct 79 ms 26340 KB Output is correct
7 Correct 113 ms 27076 KB Output is correct
8 Correct 153 ms 25060 KB Output is correct
9 Correct 61 ms 10104 KB Output is correct
10 Correct 68 ms 10536 KB Output is correct
11 Correct 73 ms 10716 KB Output is correct
12 Correct 76 ms 19728 KB Output is correct
13 Correct 115 ms 25196 KB Output is correct

Subtask #4
0 / 20.0

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