oj.uz

Submission #1076965

# Submission time Handle Problem Language Result Execution time Memory
1076965 2024-08-26T19:51:35 Z asli_bg Wall (IOI14_wall) C++11
100 / 100
 636 ms 161948 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
 
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
 
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi sp el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PDEBUG(X) { cout << #X << " = " << (X.fi) sp (X.se) << endl; }
 
#define carp(x,y) ((x%mod)*(y%mod))%mod
#define topla(x,y) ((x%mod)+(y%mod))%mod
 
const int MAXN=2e6+3;
const int INF=1e9;
const int mod=1e9+7;
 
#define mid (l+r)/2
#define endl '\n'

struct dug{
    int bir;
    int t1;
    int iki;
    int t2;
};

int n;

dug t[4*MAXN];
vi a;
int say;

void push(int nd,int l,int r){
    if(t[nd].bir==0 and t[nd].iki==INF) return;

    if(t[nd*2].bir<t[nd].bir){
        t[nd*2].bir=t[nd].bir;
        t[nd*2].t1=t[nd].t1;
    }
    if(t[nd*2].iki>t[nd].iki){
        t[nd*2].iki=t[nd].iki;
        t[nd*2].t2=t[nd].t2;
    }
    if(t[nd*2].bir>t[nd*2].iki){
        if(t[nd*2].t1>t[nd*2].t2){
            t[nd*2].iki=t[nd*2].bir;
            t[nd*2].t2=t[nd*2].t1;
        }
        else{
            t[nd*2].bir=t[nd*2].iki;
            t[nd*2].t1=t[nd*2].t2;
        }
    }
    ////////////////////////////////////////
    if(t[nd*2+1].bir<t[nd].bir){
        t[nd*2+1].bir=t[nd].bir;
        t[nd*2+1].t1=t[nd].t1;
    }
    if(t[nd*2+1].iki>t[nd].iki){
        t[nd*2+1].iki=t[nd].iki;
        t[nd*2+1].t2=t[nd].t2;
    }
    if(t[nd*2+1].bir>t[nd*2+1].iki){
        if(t[nd*2+1].t1>t[nd*2+1].t2){
            t[nd*2+1].iki=t[nd*2+1].bir;
            t[nd*2+1].t2=t[nd*2+1].t1;
        }
        else{
            t[nd*2+1].bir=t[nd*2+1].iki;
            t[nd*2+1].t1=t[nd*2+1].t2;
        }
    }

    t[nd].bir=t[nd].t1=t[nd].t2=0;
    t[nd].iki=INF;
}

int query(int pos,int nd=1,int l=1,int r=n){
    if(l==r){
        if(t[nd].bir<t[nd].iki) return t[nd].bir;
        if(t[nd].t1>t[nd].t2) return t[nd].bir;
        else return t[nd].iki;
    }
    push(nd,l,r);
    if(pos<=mid) return query(pos,nd*2,l,mid);
    else return query(pos,nd*2+1,mid+1,r);
}

void update(int ql,int qr,int h,bool f,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return;
    if(ql<=l and r<=qr){
        if(f){ //dik
            if(t[nd].bir<h){
                t[nd].bir=h;
                t[nd].t1=say;
                if(t[nd].iki!=INF and t[nd].bir>t[nd].iki){
                    t[nd].iki=t[nd].bir;
                    t[nd].t2=t[nd].t1;
                }
            }
        }
        else{ //yık
            if(t[nd].iki>h){
                t[nd].iki=h;
                t[nd].t2=say;
                if(t[nd].bir!=0 and t[nd].iki<t[nd].bir){
                    t[nd].bir=t[nd].iki;
                    t[nd].t1=t[nd].t2;
                }
            }
        }
        return;
    }
    push(nd,l,r);
    update(ql,qr,h,f,nd*2,l,mid);
    update(ql,qr,h,f,nd*2+1,mid+1,r);
}

void buildWall(int sz, int m, int opp[], int left[], int right[], int height[], int cev[]){
    n=sz;
    FOR(i,4*sz+1){
        t[i].bir=t[i].t1=t[i].t2=0;
        t[i].iki=INF;
    }

    say=1;
    FOR(i,m){
        int op=opp[i];
        int l=left[i];
        int r=right[i];
        int h=height[i];
        l++;r++;
        if(op==1){
            update(l,r,h,1);
        }
        else{
            update(l,r,h,0);
        }
        say++;
    }

    FORE(i,1,sz+1){
        cev[i-1]=query(i);
    }
    
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 388 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 84 ms 13932 KB Output is correct
3 Correct 165 ms 8528 KB Output is correct
4 Correct 440 ms 24512 KB Output is correct
5 Correct 193 ms 25684 KB Output is correct
6 Correct 192 ms 24208 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1224 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 14008 KB Output is correct
9 Correct 140 ms 8668 KB Output is correct
10 Correct 421 ms 24492 KB Output is correct
11 Correct 220 ms 25640 KB Output is correct
12 Correct 181 ms 24148 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 134 ms 13944 KB Output is correct
15 Correct 25 ms 2644 KB Output is correct
16 Correct 530 ms 24916 KB Output is correct
17 Correct 205 ms 24400 KB Output is correct
18 Correct 216 ms 24188 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 94 ms 14008 KB Output is correct
9 Correct 147 ms 8660 KB Output is correct
10 Correct 418 ms 24728 KB Output is correct
11 Correct 195 ms 25664 KB Output is correct
12 Correct 179 ms 23996 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 88 ms 14060 KB Output is correct
15 Correct 28 ms 2644 KB Output is correct
16 Correct 475 ms 24952 KB Output is correct
17 Correct 220 ms 24400 KB Output is correct
18 Correct 191 ms 24400 KB Output is correct
19 Correct 636 ms 161872 KB Output is correct
20 Correct 593 ms 159312 KB Output is correct
21 Correct 588 ms 161856 KB Output is correct
22 Correct 563 ms 159316 KB Output is correct
23 Correct 573 ms 159312 KB Output is correct
24 Correct 585 ms 159364 KB Output is correct
25 Correct 566 ms 159312 KB Output is correct
26 Correct 588 ms 161948 KB Output is correct
27 Correct 581 ms 161876 KB Output is correct
28 Correct 601 ms 159436 KB Output is correct
29 Correct 578 ms 159312 KB Output is correct
30 Correct 573 ms 159316 KB Output is correct