Submission #251945

#	Time	Username	Problem	Language	Result	Execution time	Memory
251945		NhatMinh0208	Lamps (JOI19_lamps)	C++14	0 / 100	1081 ms	35064 KiB

lamp

#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 (stderr)

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
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49