oj.uz

Submission #251945

# Submission time Handle Problem Language Result Execution time Memory
251945 2020-07-23T08:19:20 Z NhatMinh0208 Lamps (JOI19_lamps) C++14
0 / 100
 1000 ms 35064 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define ord(a,b,c) ((a>=b)and(b>=c))
#define MOD (ll(1000000007))
#define MAX 300001
#define mag 320
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pow2(x) (ll(1)<<x)
#define pii pair<int,int>
#define piii pair<int,pii>
#define pll pair<ll,ll>
#define For(i,__,___) for(int i=__;i<=___;i++)
#define Rep(i,__,___) for(int i=__;i>=___;i--)
#define ordered_set tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update>
#define endl "\n"
#define bi BigInt
typedef int ll;
//-------SEGTREE-----//
struct lazy_segment_tree{
    int seg[4 * 1000001], lazy[4 * 1000001];
    
    void down(int id, int l, int r){
        int mid = (l + r) >> 1;
        lazy[id << 1] += lazy[id];
        lazy[id << 1 | 1] += lazy[id];
        seg[id << 1] += lazy[id] ;
        seg[id << 1 | 1] += lazy[id] ;
        lazy[id] = 0;
    }
    
    void build(int id, int l, int r){
        if (l == r){
            seg[id] = 1e9;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        seg[id] = min (seg[id << 1] , seg[id << 1 | 1]);
    }
    
    void update(int id, int l, int r, int u, int v, int val){
        if (v < l || r < u){
            return;
        }
        if (u <= l && r <= v){
            seg[id] +=  val;
            lazy[id] += val;
            return;
        }
        down(id, l, r);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        seg[id] =min( seg[id << 1] , seg[id << 1 | 1]);
    }
    
    int get(int id, int l, int r, int u, int v){
        if (v < l || r < u){
            return 1e9;
        }
        if (u <= l && r <= v){
            return seg[id];
        }
        down(id, l, r);
        int mid = (l + r) >> 1;
        return min (get(id << 1, l, mid, u, v) , get(id << 1 | 1, mid + 1, r, u, v));
    }
} seg,seg0,seg1;
//---------END-------//
string s;
string t;
int n,m,i,j,k,l;
int dp[1000001], last[1000001], lastxor[1000001];
int main()
{
    cin>>n>>s>>t;
    for (i=1;i<=n;i++)
    {
        if (s[i-1]!=t[i-1]) lastxor[i]=lastxor[i-1]; else lastxor[i]=i;
    }
    last[1]=0;
    for (i=2;i<=n;i++)
    {
        if (t[i-1]==t[i-2]) last[i]=last[i-1]; else last[i]=i-1;
    }
    dp[0]=0;
    seg.build(1,0,n);
    seg.update(1,0,n,0,0,ll(-1e9));
    seg0.build(1,0,n);
    seg0.update(1,0,n,0,0,ll(-1e9));
    seg1.build(1,0,n);
    seg1.update(1,0,n,0,0,ll(-1e9));
    for (i=1;i<=n;i++)
    {
        dp[i]=1e9;
        if (s[i-1]==t[i-1]) dp[i]=dp[i-1];
        if (lastxor[i]<i)
        {
            int cand=seg.get(1,0,n,lastxor[i],i-1);
            dp[i]=min(dp[i],cand+1);
        }
        if ((t[i-1]=='0'))
        {
            if (((i<2)or(t[i-2]=='1')))
            seg1.update(1,0,n,0,i-1,1);
            else
            seg1.update(1,0,n,i-1,i-1,1);
        }
        if ((t[i-1]=='1'))
        {
            if (((i<2)or(t[i-2]=='0')))
            seg0.update(1,0,n,0,i-1,1);
            else
            seg0.update(1,0,n,i-1,i-1,1);
        }
            int cand=seg0.get(1,0,n,0,i-1);
            dp[i]=min(dp[i],cand+1);
                cand=seg1.get(1,0,n,0,i-1);
            dp[i]=min(dp[i],cand+1);
        seg.update(1,0,n,i,i,dp[i]-ll(1e9));
        seg0.update(1,0,n,i,i,dp[i]-ll(1e9));
        seg1.update(1,0,n,i,i,dp[i]-ll(1e9));
    }
    cout<<dp[n];
}

Compilation message

lamp.cpp:8:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
lamp.cpp: In member function 'void lazy_segment_tree::down(int, int, int)':
lamp.cpp:42:13: warning: unused variable 'mid' [-Wunused-variable]
         int mid = (l + r) >> 1;
             ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Incorrect 0 ms 384 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Incorrect 0 ms 384 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Execution timed out 1081 ms 35064 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Incorrect 0 ms 384 KB Output isn't correct
14 Halted 0 ms 0 KB -