| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 239970 | Fasho | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define N 200005
#define ll long long int
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
#include "paint.h"
using namespace std;
ll n,m,ar[N],sum,t,tut[N],tree[6*N],tutb[N],lazy[6*N],pref[N],flag;
ll dp[200100][150];
string att,sss;
void push(int ind,int l,int r)
{
ll x=lazy[ind];
tree[ind]+=x;
lazy[ind]=0;
if(l==r)
return;
lazy[ind*2]+=x;
lazy[ind*2+1]+=x;
}
ll query(ll ind,ll l,ll r,ll a)
{
if(l>a || r<a)
return 0;
push(ind,l,r);
if(l==r)
return tree[ind];
int mid=(l+r)/2;
ll x=query(ind*2,l,mid,a);
ll y=query(ind*2+1,mid+1,r,a);
if(a<=mid)
return x;
else
return y;
return max(x,y);
}
void upd(int ind,int l,int r,int a,int b,ll val)
{
if(l>b || r<a)
return;
push(ind,l,r);
if(l>=a && r<=b)
{
lazy[ind]+=val;
push(ind,l,r);
return;
}
int mid=(l+r)/2;
upd(ind*2,l,mid,a,b,val);
upd(ind*2+1,mid+1,r,a,b,val);
}
ll f(int ind,int k)
{
if(ind>n)
return 0;
if(ind==n && k==m)
{
// cerr<<"hello"<<endl;
return 1;
}
if(k>m)
return 0;
if(ind==n)
return 0;
// cerr<<ind<<sp<<k<<endl;
if(dp[ind][k]!=-1)
return dp[ind][k];
ll a=0;
if(sss[ind]!='X')
a=f(ind+1,k);
ll x=0;
ll b=0;
if(ind>0)
x=pref[ind-1];
if(ind+ar[k]<=n && pref[ind+ar[k]-1]-x==0 && sss[ind+ar[k]]!='X' && sss[ind]!='_')
{
if(ind+ar[k]==n)
b=f(ind+ar[k],k+1);
else
b=f(ind+ar[k]+1,k+1);
}
// cout<<ind<<sp<<k<<sp<<a<<sp<<b<<endl;
if(sss[ind]=='_')
{
tutb[ind]=a;
return dp[ind][k]=a;
}
if(b)
tutb[ind+ar[k]]=1;
if(sss[ind]=='X')
{
updateRangeUtil(1,0,n-1,ind,ind+ar[k]-1,b);
return dp[ind][k]=b;
}
tutb[ind]=a;
// if(b)
// cout<<"X"<<sp<<ind<<sp<<k<<endl;
// if(a)
// cout<<"_"<<sp<<ind<<sp<<k<<endl;
updateRangeUtil(1,0,n-1,ind,ind+ar[k]-1,b);
if(ind==0 && b)
flag=1;
return dp[ind][k]=a+b;
}
void updateRangeUtil(int si, int ss, int se, int us,
int ue, int diff)
{
// If lazy value is non-zero for current node of segment
// tree, then there are some pending updates. So we need
// to make sure that the pending updates are done before
// making new updates. Because this value may be used by
// parent after recursive calls (See last line of this
// function)
if (lazy[si] != 0)
{
// Make pending updates using value stored in lazy
// nodes
tree[si] += (se-ss+1)*lazy[si];
// checking if it is not leaf node because if
// it is leaf node then we cannot go further
if (ss != se)
{
// We can postpone updating children we don't
// need their new values now.
// Since we are not yet updating children of si,
// we need to set lazy flags for the children
lazy[si*2 + 1] += lazy[si];
lazy[si*2 + 2] += lazy[si];
}
// Set the lazy value for current node as 0 as it
// has been updated
lazy[si] = 0;
}
// out of range
if (ss>se || ss>ue || se<us)
return ;
// Current segment is fully in range
if (ss>=us && se<=ue)
{
// Add the difference to current node
tree[si] += (se-ss+1)*diff;
// same logic for checking leaf node or not
if (ss != se)
{
// This is where we store values in lazy nodes,
// rather than updating the segment tree itelf
// Since we don't need these updated values now
// we postpone updates by storing values in lazy[]
lazy[si*2 + 1] += diff;
lazy[si*2 + 2] += diff;
}
return;
}
}
int getSumUtil(int ss, int se, int qs, int qe, int si)
{
// If lazy flag is set for current node of segment tree,
// then there are some pending updates. So we need to
// make sure that the pending updates are done before
// processing the sub sum query
if (lazy[si] != 0)
{
// Make pending updates to this node. Note that this
// node represents sum of elements in arr[ss..se] and
// all these elements must be increased by lazy[si]
tree[si] += (se-ss+1)*lazy[si];
// checking if it is not leaf node because if
// it is leaf node then we cannot go further
if (ss != se)
{
// Since we are not yet updating children os si,
// we need to set lazy values for the children
lazy[si*2+1] += lazy[si];
lazy[si*2+2] += lazy[si];
}
// unset the lazy value for current node as it has
// been updated
lazy[si] = 0;
}
// Out of range
if (ss>se || ss>qe || se<qs)
return 0;
// At this point we are sure that pending lazy updates
// are done for current node. So we can return value
// (same as it was for query in our previous post)
// If this segment lies in range
if (ss>=qs && se<=qe)
return tree[si];
// If a part of this segment overlaps with the given
// range
int mid = (ss + se)/2;
return getSumUtil(ss, mid, qs, qe, 2*si+1) +
getSumUtil(mid+1, se, qs, qe, 2*si+2);
}
string solve_puzzle(string ss,vector<int> c)
{
m=c.size();
fo(i,0,m-1)
ar[i]=c[i];
n=ss.size();
sss=ss;
memset(dp,-1,sizeof(dp));
memset(tree,0,sizeof(tree));
memset(lazy,0,sizeof(lazy));
fo(i,0,n)
{
pref[i]=pref[i-1];
if(sss[i]=='_')
pref[i]++;
}
f(0,0);
att.clear();
fo(i,0,n-1)
{
ll x=query(1,0,n-1,i);
ll y=tutb[i];
if(x && !y)
att.pb('X');
if(!x && y)
att.pb('_');
if(att.size()!=i+1)
att.pb('?');
}
char a='0'+getSumUtil(1,0,n-1,0);
// char a='0'+flag;
string b;
b.pb(a);
fo(i,1,12)
b.pb('a');
// cout<<ar[0]<<endl;;
return b;
// return "?????XXX?????";
return att;
}
vector<int> v;
// int main()
// {
// fast;
// cin>>sss>>n;
// fo(i,1,n)
// {
// int a;
// cin>>a;
// v.pb(a);
// }
// cout<<solve_puzzle(sss,v);
// }
// #include "paint.h"
// #include <vector>
// #include <string>
// #include <cstdio>
// #include <cassert>
// const int S_MAX_LEN = 200 * 1000;
// char buf[S_MAX_LEN + 1];
// int main() {
// assert(1 == scanf("%s", buf));
// std::string s = buf;
// int c_len;
// assert(1 == scanf("%d", &c_len));
// std::vector<int> c(c_len);
// for (int i = 0; i < c_len; i++) {
// assert(1 == scanf("%d", &c[i]));
// }
// std::string ans = solve_puzzle(s, c);
// printf("%s\n", ans.data());
// return 0;
// }