oj.uz

Submission #245097

# Submission time Handle Problem Language Result Execution time Memory
245097 2020-07-05T13:26:29 Z Fasho Wall (IOI14_wall) C++14
100 / 100
 1035 ms 172664 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62968 KB Output is correct
2 Correct 38 ms 62968 KB Output is correct
3 Correct 37 ms 63104 KB Output is correct
4 Correct 46 ms 63616 KB Output is correct
5 Correct 42 ms 63612 KB Output is correct
6 Correct 42 ms 63616 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62976 KB Output is correct
2 Correct 204 ms 70824 KB Output is correct
3 Correct 272 ms 67576 KB Output is correct
4 Correct 743 ms 75768 KB Output is correct
5 Correct 452 ms 76408 KB Output is correct
6 Correct 446 ms 76408 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62968 KB Output is correct
2 Correct 37 ms 62968 KB Output is correct
3 Correct 38 ms 62976 KB Output is correct
4 Correct 43 ms 63608 KB Output is correct
5 Correct 43 ms 63608 KB Output is correct
6 Correct 41 ms 63608 KB Output is correct
7 Correct 38 ms 62840 KB Output is correct
8 Correct 205 ms 70776 KB Output is correct
9 Correct 277 ms 67448 KB Output is correct
10 Correct 745 ms 75768 KB Output is correct
11 Correct 462 ms 76280 KB Output is correct
12 Correct 448 ms 76280 KB Output is correct
13 Correct 36 ms 62968 KB Output is correct
14 Correct 231 ms 70776 KB Output is correct
15 Correct 74 ms 64632 KB Output is correct
16 Correct 734 ms 76056 KB Output is correct
17 Correct 452 ms 76024 KB Output is correct
18 Correct 446 ms 76024 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62976 KB Output is correct
2 Correct 38 ms 62968 KB Output is correct
3 Correct 37 ms 62976 KB Output is correct
4 Correct 45 ms 63608 KB Output is correct
5 Correct 42 ms 63608 KB Output is correct
6 Correct 41 ms 63608 KB Output is correct
7 Correct 39 ms 62968 KB Output is correct
8 Correct 212 ms 70776 KB Output is correct
9 Correct 276 ms 67448 KB Output is correct
10 Correct 775 ms 75964 KB Output is correct
11 Correct 453 ms 76280 KB Output is correct
12 Correct 443 ms 76408 KB Output is correct
13 Correct 41 ms 62968 KB Output is correct
14 Correct 210 ms 70776 KB Output is correct
15 Correct 80 ms 64632 KB Output is correct
16 Correct 789 ms 76152 KB Output is correct
17 Correct 431 ms 76024 KB Output is correct
18 Correct 452 ms 76152 KB Output is correct
19 Correct 1034 ms 162296 KB Output is correct
20 Correct 1035 ms 170104 KB Output is correct
21 Correct 1029 ms 172664 KB Output is correct
22 Correct 1029 ms 170232 KB Output is correct
23 Correct 1016 ms 170236 KB Output is correct
24 Correct 1030 ms 170220 KB Output is correct
25 Correct 1032 ms 169960 KB Output is correct
26 Correct 1020 ms 172408 KB Output is correct
27 Correct 1020 ms 172548 KB Output is correct
28 Correct 1000 ms 170104 KB Output is correct
29 Correct 1012 ms 169908 KB Output is correct
30 Correct 1004 ms 170104 KB Output is correct