Submission #239970

#	Time	Username	Problem	Language	Result	Execution time	Memory
239970		Fasho	Paint By Numbers (IOI16_paint)	C++14	Compilation error	0 ms	0 KiB

paint

#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;
// }

Compilation message (stderr)

paint.cpp: In function 'long long int f(int, int)':
paint.cpp:115:3: error: 'updateRangeUtil' was not declared in this scope
   updateRangeUtil(1,0,n-1,ind,ind+ar[k]-1,b);
   ^~~~~~~~~~~~~~~
paint.cpp:123:2: error: 'updateRangeUtil' was not declared in this scope
  updateRangeUtil(1,0,n-1,ind,ind+ar[k]-1,b);
  ^~~~~~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:261:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(att.size()!=i+1)
      ~~~~~~~~~~^~~~~
paint.cpp:264:33: error: too few arguments to function 'int getSumUtil(int, int, int, int, int)'
  char a='0'+getSumUtil(1,0,n-1,0);
                                 ^
paint.cpp:187:8: note: declared here
    int getSumUtil(int ss, int se, int qs, int qe, int si) 
        ^~~~~~~~~~