| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 818653 | 2023-08-10T06:06:51 Z | vjudge1 | Crossing (JOI21_crossing) | C++17 | 140 ms | 940 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 fi first
#define se second
#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 = 6e5 + 9 , mod = 1e9 + 7;
ll d[N] , a[N][5] = {}, dp[N] , b[N] , c[N] , bl[N] , cnt[N][5] , sz[N] , tree[N];
map<char, int >mp;
ll check(int l , int r){
for(int j = 1; j <= 3; j++)
if((a[r][j] - a[r - 1][j]) != 0 && (a[r][j] - a[l - 1][j]) == r - l + 1)
return j;
return 0;
}
set<ll>st;
void build(int i , int l , int r){
bl[i] = check(l , r);
sz[i] = r - l + 1;
if(bl[i]){ st.insert(i) ; return; }
ll m = (l + r) / 2;
build(2 * i , l , m);
build(2 * i + 1 , m + 1 , r);
}
ll ans =0;
void check1(int i){
if(bl[i] && sz[i] == cnt[i][bl[i]])
if(st.find(i) != st.end())
st.erase(i);
}
void lazy(int i ,int l , int r){
if(tree[i]){
if(bl[i])
st.insert(i);
cnt[i][1] = cnt[i][2] = cnt[i][3] = 0;
cnt[i][tree[i]] = r - l + 1;
check1(i);
tree[2 * i] = tree[2 * i + 1] = tree[i];
tree[i] = 0;
}
}
void pushup(int i){
for(int j = 1; j <= 3; j++)
cnt[i][j] = cnt[2 * i][j] +cnt[2 * i + 1][j];
if(bl[i])
st.insert(i);
check1(i);
}
void add(int i , int l , int r ,int x , int y , int k){
lazy(i , l , r);
if(l > y || r < x || l > r)
return;
if(l >= x && r <= y){
tree[i] = k;
lazy(i , l , r);
return;
}
ll m = (l + r) / 2;
add(2 * i , l , m, x , y , k);
add(2 * i + 1 , m + 1 , r, x , y , k);
pushup(i);
}
void solve(){
ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn = 1e18 , mx = 0;
cin>>n;
string a , b , c;
cin>>a>>b>>c;
mp['J'] = 1 ;
mp['O'] = 2 ;
mp['I'] = 3 ;
for(i = 1; i <= n; i++){
for(j = 1; j <= 3; j++){
::a[i][j] = ::a[i - 1][j];
}
::a[i][mp[a[i - 1]]]++;
}
if(a == b && b == c){
string c;
cin>>q;
cin>>c;
build(1 , 1 , n);
for(i = 1; i <= n; i++){
// cout<<mp[c[i - 1]]<<"\n";
add(1 , 1 , n , i , i , mp[c[i - 1]]);
// cout<<st.size()<<"\n";
}
(st.size() == 0 ? Yes : No);
while(q--){
char ch;
cin>>l>>r>>ch;
add(1 , 1 , n , l , r , mp[ch]);
//cout<<st.size()<<"\n';
(st.size() == 0 ? Yes : No);
}
return;
}
}
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 | 108 ms | 904 KB | Output is correct |
| 2 | Correct | 140 ms | 940 KB | Output is correct |
| 3 | Correct | 110 ms | 932 KB | Output is correct |
| 4 | Incorrect | 118 ms | 936 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 108 ms | 904 KB | Output is correct |
| 2 | Correct | 140 ms | 940 KB | Output is correct |
| 3 | Correct | 110 ms | 932 KB | Output is correct |
| 4 | Incorrect | 118 ms | 936 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 108 ms | 904 KB | Output is correct |
| 2 | Correct | 140 ms | 940 KB | Output is correct |
| 3 | Correct | 110 ms | 932 KB | Output is correct |
| 4 | Incorrect | 118 ms | 936 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 108 ms | 904 KB | Output is correct |
| 2 | Correct | 140 ms | 940 KB | Output is correct |
| 3 | Correct | 110 ms | 932 KB | Output is correct |
| 4 | Incorrect | 118 ms | 936 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |