oj.uz

Submission #243721

# Submission time Handle Problem Language Result Execution time Memory
243721 2020-07-01T16:11:07 Z Fasho Wall (IOI14_wall) C++14
61 / 100
 1077 ms 143564 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 31744 KB Output is correct
2 Correct 24 ms 31744 KB Output is correct
3 Correct 22 ms 31744 KB Output is correct
4 Correct 27 ms 32512 KB Output is correct
5 Correct 28 ms 32376 KB Output is correct
6 Correct 26 ms 32384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31608 KB Output is correct
2 Correct 193 ms 45348 KB Output is correct
3 Correct 250 ms 39928 KB Output is correct
4 Correct 834 ms 54028 KB Output is correct
5 Correct 433 ms 55288 KB Output is correct
6 Correct 423 ms 53604 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31616 KB Output is correct
2 Correct 21 ms 31744 KB Output is correct
3 Correct 20 ms 31744 KB Output is correct
4 Correct 28 ms 32512 KB Output is correct
5 Correct 26 ms 32552 KB Output is correct
6 Correct 26 ms 32384 KB Output is correct
7 Correct 19 ms 31616 KB Output is correct
8 Correct 190 ms 45304 KB Output is correct
9 Correct 267 ms 40008 KB Output is correct
10 Correct 737 ms 54108 KB Output is correct
11 Correct 443 ms 55096 KB Output is correct
12 Correct 430 ms 53672 KB Output is correct
13 Correct 22 ms 31616 KB Output is correct
14 Correct 187 ms 45304 KB Output is correct
15 Correct 61 ms 34040 KB Output is correct
16 Correct 709 ms 54392 KB Output is correct
17 Correct 431 ms 53880 KB Output is correct
18 Correct 437 ms 53748 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31616 KB Output is correct
2 Correct 23 ms 31744 KB Output is correct
3 Correct 21 ms 31744 KB Output is correct
4 Correct 28 ms 32504 KB Output is correct
5 Correct 29 ms 32376 KB Output is correct
6 Correct 28 ms 32376 KB Output is correct
7 Correct 22 ms 31616 KB Output is correct
8 Correct 195 ms 45352 KB Output is correct
9 Correct 253 ms 39928 KB Output is correct
10 Correct 714 ms 54136 KB Output is correct
11 Correct 431 ms 55268 KB Output is correct
12 Correct 419 ms 53492 KB Output is correct
13 Correct 23 ms 31616 KB Output is correct
14 Correct 200 ms 45432 KB Output is correct
15 Correct 59 ms 33912 KB Output is correct
16 Correct 883 ms 54348 KB Output is correct
17 Correct 449 ms 53728 KB Output is correct
18 Correct 467 ms 53704 KB Output is correct
19 Incorrect 1077 ms 143564 KB Output isn't correct
20 Halted 0 ms 0 KB -