| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 983169 | 2024-05-15T08:54:27 Z | vjudge1 | Street Lamps (APIO19_street_lamps) | C++17 | 129 ms | 26704 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){
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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 10584 KB | Output is correct |
| 2 | Correct | 1 ms | 8540 KB | Output is correct |
| 3 | Correct | 1 ms | 8540 KB | Output is correct |
| 4 | Correct | 1 ms | 8540 KB | Output is correct |
| 5 | Correct | 1 ms | 10588 KB | Output is correct |
| 6 | Correct | 1 ms | 6492 KB | Output is correct |
| 7 | Correct | 1 ms | 6492 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 52 ms | 9492 KB | Output is correct |
| 2 | Correct | 53 ms | 7480 KB | Output is correct |
| 3 | Correct | 58 ms | 7508 KB | Output is correct |
| 4 | Correct | 100 ms | 23104 KB | Output is correct |
| 5 | Correct | 93 ms | 22504 KB | Output is correct |
| 6 | Correct | 74 ms | 23264 KB | Output is correct |
| 7 | Correct | 82 ms | 13760 KB | Output is correct |
| 8 | Correct | 79 ms | 19176 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 8536 KB | Output is correct |
| 2 | Correct | 1 ms | 8540 KB | Output is correct |
| 3 | Correct | 2 ms | 8536 KB | Output is correct |
| 4 | Correct | 1 ms | 6492 KB | Output is correct |
| 5 | Correct | 67 ms | 25436 KB | Output is correct |
| 6 | Correct | 71 ms | 26152 KB | Output is correct |
| 7 | Correct | 80 ms | 26704 KB | Output is correct |
| 8 | Correct | 121 ms | 24808 KB | Output is correct |
| 9 | Correct | 65 ms | 10068 KB | Output is correct |
| 10 | Correct | 66 ms | 10580 KB | Output is correct |
| 11 | Correct | 79 ms | 10608 KB | Output is correct |
| 12 | Correct | 81 ms | 19424 KB | Output is correct |
| 13 | Correct | 129 ms | 24764 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 10584 KB | Output is correct |
| 2 | Incorrect | 2 ms | 8540 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 10584 KB | Output is correct |
| 2 | Correct | 1 ms | 8540 KB | Output is correct |
| 3 | Correct | 1 ms | 8540 KB | Output is correct |
| 4 | Correct | 1 ms | 8540 KB | Output is correct |
| 5 | Correct | 1 ms | 10588 KB | Output is correct |
| 6 | Correct | 1 ms | 6492 KB | Output is correct |
| 7 | Correct | 1 ms | 6492 KB | Output is correct |
| 8 | Correct | 52 ms | 9492 KB | Output is correct |
| 9 | Correct | 53 ms | 7480 KB | Output is correct |
| 10 | Correct | 58 ms | 7508 KB | Output is correct |
| 11 | Correct | 100 ms | 23104 KB | Output is correct |
| 12 | Correct | 93 ms | 22504 KB | Output is correct |
| 13 | Correct | 74 ms | 23264 KB | Output is correct |
| 14 | Correct | 82 ms | 13760 KB | Output is correct |
| 15 | Correct | 79 ms | 19176 KB | Output is correct |
| 16 | Correct | 1 ms | 8536 KB | Output is correct |
| 17 | Correct | 1 ms | 8540 KB | Output is correct |
| 18 | Correct | 2 ms | 8536 KB | Output is correct |
| 19 | Correct | 1 ms | 6492 KB | Output is correct |
| 20 | Correct | 67 ms | 25436 KB | Output is correct |
| 21 | Correct | 71 ms | 26152 KB | Output is correct |
| 22 | Correct | 80 ms | 26704 KB | Output is correct |
| 23 | Correct | 121 ms | 24808 KB | Output is correct |
| 24 | Correct | 65 ms | 10068 KB | Output is correct |
| 25 | Correct | 66 ms | 10580 KB | Output is correct |
| 26 | Correct | 79 ms | 10608 KB | Output is correct |
| 27 | Correct | 81 ms | 19424 KB | Output is correct |
| 28 | Correct | 129 ms | 24764 KB | Output is correct |
| 29 | Correct | 2 ms | 10584 KB | Output is correct |
| 30 | Incorrect | 2 ms | 8540 KB | Output isn't correct |
| 31 | Halted | 0 ms | 0 KB | - |