oj.uz

Submission #819178

# Submission time Handle Problem Language Result Execution time Memory
819178 2023-08-10T08:19:46 Z vjudge1 Crossing (JOI21_crossing) C++17
0 / 100
 180 ms 2260 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 = 1e5 + 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){
    if(l <= 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);
    ll m = (l + r) / 2;
    lazy(2 * i , l , m);
    lazy(2 * i + 1 , m + 1 , r);
    if(l > y || r < x || l > r)
        return;
    if(l >= x && r <= y){
        tree[i] = k;
        lazy(i , l , r);
        lazy(2 * i , l , m);
        lazy(2 * i + 1 , m + 1 , r);
        return;
    }
    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 ;
    if(n <= 5){
        cin>>q;
        cin>>c;
        if(c == a) Yes;
        else
            No;
        while(q--){
            char ch;
            cin>>l>>r>>ch;
            for(i = l - 1; i < r; i++)
                c[i] = ch;

        if(c == a) Yes;
        else
            No;
        }
        return;
        }
    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++)
            add(1 , 1 , n , i , i , mp[c[i - 1]]);
        (st.size() == 0 ? Yes : No);
        while(q--){
            char ch;
            cin>>l>>r>>ch;
            add(1 , 1 , n , l , r , mp[ch]);
            (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

Main.cpp: In function 'void solve()':
Main.cpp:95:20: warning: unused variable 'm' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                    ^
Main.cpp:95:26: warning: unused variable 'z' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
Main.cpp:95:29: warning: unused variable 's' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
Main.cpp:95:37: warning: unused variable 'f' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
Main.cpp:95:49: warning: unused variable 'k' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                 ^
Main.cpp:95:53: warning: unused variable 'x' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                     ^
Main.cpp:95:57: warning: unused variable 'y' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                         ^
Main.cpp:95:61: warning: unused variable 'mn' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                             ^~
Main.cpp:95:74: warning: unused variable 'mx' [-Wunused-variable]
   95 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                          ^~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 2168 KB Output is correct
2 Correct 180 ms 2168 KB Output is correct
3 Correct 164 ms 2260 KB Output is correct
4 Incorrect 126 ms 2244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 2168 KB Output is correct
2 Correct 180 ms 2168 KB Output is correct
3 Correct 164 ms 2260 KB Output is correct
4 Incorrect 126 ms 2244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 2168 KB Output is correct
2 Correct 180 ms 2168 KB Output is correct
3 Correct 164 ms 2260 KB Output is correct
4 Incorrect 126 ms 2244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 2168 KB Output is correct
2 Correct 180 ms 2168 KB Output is correct
3 Correct 164 ms 2260 KB Output is correct
4 Incorrect 126 ms 2244 KB Output isn't correct
5 Halted 0 ms 0 KB -