oj.uz

Submission #318013

# Submission time Handle Problem Language Result Execution time Memory
318013 2020-10-31T07:38:07 Z zaneyu Wall (IOI14_wall) C++14
100 / 100
 1739 ms 69860 KB 
/*input
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
 
*/
//#include "wall.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ll long long 
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define MP make_pair
const ll INF64=4e12;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1){
            res=(res*a)%MOD;
        }
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
//mn: at least
//mx: at most
struct node{
    int mn=0,mx=INF;
}seg[(1<<22)];
//starts to be available 
void pushdown(int idx,int l,int r){
    if(l==r) return;
    seg[idx*2].mn=max(seg[idx].mn,min(seg[idx*2].mn,seg[idx].mx));
    seg[idx*2].mx=min(seg[idx].mx,max(seg[idx*2].mx,seg[idx].mn));
    seg[idx*2+1].mn=max(seg[idx].mn,min(seg[idx*2+1].mn,seg[idx].mx));
    seg[idx*2+1].mx=min(seg[idx].mx,max(seg[idx*2+1].mx,seg[idx].mn));
    seg[idx].mn=0,seg[idx].mx=INF;
}
void upd(int idx,int l,int r,int ql,int qr,int tp,int x){
    pushdown(idx,l,r);
    if(r<ql or l>qr) return;
    if(ql<=l and r<=qr){
        if(tp==0){
            MXTO(seg[idx].mx,x);
            MXTO(seg[idx].mn,x);
        }
        else{
            MNTO(seg[idx].mn,x);
            MNTO(seg[idx].mx,x);
        }
        pushdown(idx,l,r);
        return;
    }
    int mid=(l+r)/2;
    upd(idx*2,l,mid,ql,qr,tp,x);
    upd(idx*2+1,mid+1,r,ql,qr,tp,x);
}
/*void traverse(int idx,int l,int r){
    cout<<l<<' '<<r<<' '<<seg[idx].mn<<' '<<seg[idx].mx<<'\n';
    if(l==r) return;
    int mid=(l+r)/2;
    traverse(idx*2,l,mid);
    traverse(idx*2+1,mid+1,r);
}*/
int query(int idx,int l,int r,int p){
    pushdown(idx,l,r);
    if(l>p or r<p) return 0;
    if(l==r){
        //cout<<seg[idx].mn<<' '<<seg[idx].mx<<'\n';
        return seg[idx].mn;
    }
    int mid=(l+r)/2;
    return query(idx*2,l,mid,p)+query(idx*2+1,mid+1,r,p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    REP(i,k){
        upd(1,0,n-1,left[i],right[i],op[i]-1,height[i]);
        /*traverse(1,0,n-1);
        cout<<'\n';*/
    }
    REP(i,n){
        finalHeight[i]=query(1,0,n-1,i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 9 ms 876 KB Output is correct
6 Correct 9 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 170 ms 8292 KB Output is correct
3 Correct 250 ms 4324 KB Output is correct
4 Correct 680 ms 10916 KB Output is correct
5 Correct 424 ms 11516 KB Output is correct
6 Correct 417 ms 11492 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 9 ms 876 KB Output is correct
6 Correct 10 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 171 ms 8420 KB Output is correct
9 Correct 275 ms 4580 KB Output is correct
10 Correct 695 ms 10920 KB Output is correct
11 Correct 425 ms 11524 KB Output is correct
12 Correct 414 ms 11496 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 170 ms 8676 KB Output is correct
15 Correct 46 ms 1636 KB Output is correct
16 Correct 767 ms 11236 KB Output is correct
17 Correct 422 ms 11236 KB Output is correct
18 Correct 421 ms 11364 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 10 ms 876 KB Output is correct
5 Correct 9 ms 876 KB Output is correct
6 Correct 9 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 165 ms 8288 KB Output is correct
9 Correct 251 ms 4324 KB Output is correct
10 Correct 676 ms 10920 KB Output is correct
11 Correct 483 ms 11432 KB Output is correct
12 Correct 410 ms 11492 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 166 ms 8292 KB Output is correct
15 Correct 44 ms 1636 KB Output is correct
16 Correct 775 ms 11236 KB Output is correct
17 Correct 417 ms 11236 KB Output is correct
18 Correct 419 ms 11164 KB Output is correct
19 Correct 1739 ms 59456 KB Output is correct
20 Correct 1700 ms 67176 KB Output is correct
21 Correct 1729 ms 69860 KB Output is correct
22 Correct 1696 ms 67300 KB Output is correct
23 Correct 1693 ms 67348 KB Output is correct
24 Correct 1695 ms 67172 KB Output is correct
25 Correct 1693 ms 67300 KB Output is correct
26 Correct 1691 ms 69604 KB Output is correct
27 Correct 1695 ms 69604 KB Output is correct
28 Correct 1701 ms 67044 KB Output is correct
29 Correct 1707 ms 67044 KB Output is correct
30 Correct 1692 ms 67044 KB Output is correct