Submission #245097

#	Time	Username	Problem	Language	Result	Execution time	Memory
245097		Fasho	Wall (IOI14_wall)	C++14	100 / 100	1035 ms	172664 KiB

wall

#include <bits/stdc++.h>
#define N 2000005
#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

// #define left lef
// #define right rig
 
using namespace std;
 
ll m,ar[N],sum,t,mn[4*N],mx[4*N];
lli lazy[4*N];
ll tree[6*N];
// int n,  k,  op[N],  lft[N],  rght[N],  height[N];
ll ans[N]; 
// void push(int l,int r,ll ind)
// {
// 	 if(l==r) tree[ind] = max(tree[ind],lazy[ind].fi),tree[ind] = min(tree[ind],lazy[ind].se);
// 	if(l!=r)
//     {
//         lazy[ind*2].fi = max(lazy[ind*2].fi,lazy[ind].fi),lazy[ind*2].se = max(lazy[ind*2].se,lazy[ind].fi);
//         lazy[ind*2+1].fi = max(lazy[ind*2+1].fi,lazy[ind].fi),lazy[ind*2+1].se = max(lazy[ind*2+1].se,lazy[ind].fi);
//         lazy[ind*2].se = min(lazy[ind*2].se,lazy[ind].se),lazy[ind*2].fi = min(lazy[ind*2].fi,lazy[ind].se);
//         lazy[ind*2+1].se = min(lazy[ind*2+1].se,lazy[ind].se),lazy[ind*2+1].fi = min(lazy[ind*2+1].fi,lazy[ind].se);
//     }
// 	lazy[ind]={-1e16,1e16};
// }
void push(int l,int r,int idx)
{
    if(l==r) tree[idx] = max(tree[idx],mn[idx]),tree[idx] = min(tree[idx],mx[idx]);
    else
    {
        mn[idx*2] = max(mn[idx*2],mn[idx]),mx[idx*2] = max(mx[idx*2],mn[idx]);
        mn[idx*2+1] = max(mn[idx*2+1],mn[idx]),mx[idx*2+1] = max(mx[idx*2+1],mn[idx]);
        mx[idx*2] = min(mx[idx*2],mx[idx]),mn[idx*2] = min(mn[idx*2],mx[idx]);
        mx[idx*2+1] = min(mx[idx*2+1],mx[idx]),mn[idx*2+1] = min(mn[idx*2+1],mx[idx]);
    }
    mn[idx] = INT_MIN,mx[idx] = INT_MAX;
}
// void update(int l,int r,int idx,int t,int x,int y,int k)
// {
//     push(idx,l,r);
//     if(x>r or y<l) return;
//     if(x<=l and y>=r)
//     {
//         if(t==1) lazy[idx].fi = k;
//         else lazy[idx].se = k;
//         push(idx,l,r);
//         return;
//     }
//     int m = (l+r)/2;
//     update(l,m,idx*2,t,x,y,k),update(m+1,r,idx*2+1,t,x,y,k);
// }
void update(int l,int r,int idx,int t,int x,int y,int k)
{
    push(l,r,idx);
    if(x>r or y<l) return;
    if(x<=l and y>=r)
    {
        if(t==1) mn[idx] = k;
        else mx[idx] = k;
        push(l,r,idx);
        return;
    }
    int m = (l+r)/2;
    update(l,m,idx*2,t,x,y,k),update(m+1,r,idx*2+1,t,x,y,k);
}

void pushlz(int l,int r,int ind)
{
    push(l,r,ind);
    if(l==r) return void(ans[l] = tree[ind]);
    int m = (l+r)/2;
    pushlz(l,m,ind*2),pushlz(m+1,r,ind*2+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	fo(i,0,4*N-1)
		mx[i]=1e16;
	fo(i,0,k-1)
		update(1,n,1,op[i],left[i]+1,right[i]+1,height[i]);
 	pushlz(1,n,1);
  	fo(i,1,n)
		finalHeight[i-1]=ans[i];
}

 
 
 
// int main()
// {
//   int n;
//   int k;

//   int i, j;  
//   int status = 0;

//   status = scanf("%d%d", &n, &k);
//   assert(status == 2);

//   int* op = (int*)calloc(sizeof(int), k);
//   int* left = (int*)calloc(sizeof(int), k);
//   int* right = (int*)calloc(sizeof(int), k);
//   int* height = (int*)calloc(sizeof(int), k);
//   int* finalHeight = (int*)calloc(sizeof(int), n);

//   for (i = 0; i < k; i++){
//     status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
//     assert(status == 4);
//   }

//   buildWall(n, k, op, left, right, height, finalHeight);

//   for (j = 0; j < n; j++)
//     printf("%d\n", finalHeight[j]);
  
//   return 0;
// }

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39