oj.uz

Submission #245096

# Submission time Handle Problem Language Result Execution time Memory
245096 2020-07-05T13:25:28 Z Fasho Wall (IOI14_wall) C++14
61 / 100
 1012 ms 143608 KB 
#include <bits/stdc++.h>
#define N 1000005
#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 20 ms 31616 KB Output is correct
2 Correct 22 ms 31744 KB Output is correct
3 Correct 21 ms 31744 KB Output is correct
4 Correct 29 ms 32504 KB Output is correct
5 Correct 26 ms 32512 KB Output is correct
6 Correct 27 ms 32512 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31616 KB Output is correct
2 Correct 195 ms 45284 KB Output is correct
3 Correct 257 ms 39928 KB Output is correct
4 Correct 798 ms 54264 KB Output is correct
5 Correct 439 ms 55160 KB Output is correct
6 Correct 433 ms 53244 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31608 KB Output is correct
2 Correct 22 ms 31744 KB Output is correct
3 Correct 22 ms 31744 KB Output is correct
4 Correct 28 ms 32512 KB Output is correct
5 Correct 29 ms 32512 KB Output is correct
6 Correct 26 ms 32384 KB Output is correct
7 Correct 21 ms 31616 KB Output is correct
8 Correct 195 ms 45312 KB Output is correct
9 Correct 271 ms 39928 KB Output is correct
10 Correct 806 ms 54136 KB Output is correct
11 Correct 435 ms 55288 KB Output is correct
12 Correct 422 ms 53624 KB Output is correct
13 Correct 20 ms 31592 KB Output is correct
14 Correct 197 ms 45364 KB Output is correct
15 Correct 57 ms 33912 KB Output is correct
16 Correct 749 ms 54392 KB Output is correct
17 Correct 431 ms 53880 KB Output is correct
18 Correct 443 ms 53720 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31616 KB Output is correct
2 Correct 26 ms 31744 KB Output is correct
3 Correct 22 ms 31744 KB Output is correct
4 Correct 32 ms 32504 KB Output is correct
5 Correct 28 ms 32504 KB Output is correct
6 Correct 27 ms 32384 KB Output is correct
7 Correct 23 ms 31616 KB Output is correct
8 Correct 192 ms 45304 KB Output is correct
9 Correct 253 ms 39928 KB Output is correct
10 Correct 728 ms 54140 KB Output is correct
11 Correct 442 ms 55160 KB Output is correct
12 Correct 428 ms 53496 KB Output is correct
13 Correct 20 ms 31616 KB Output is correct
14 Correct 199 ms 45308 KB Output is correct
15 Correct 59 ms 33912 KB Output is correct
16 Correct 770 ms 54392 KB Output is correct
17 Correct 435 ms 53756 KB Output is correct
18 Correct 492 ms 53772 KB Output is correct
19 Incorrect 1012 ms 143608 KB Output isn't correct
20 Halted 0 ms 0 KB -