oj.uz

Submission #254170

# Submission time Handle Problem Language Result Execution time Memory
254170 2020-07-29T12:42:17 Z PedroBigMan Wall (IOI14_wall) C++14
8 / 100
 209 ms 9500 KB 
#include "wall.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159

class ST1
{
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=0;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(min(a,X.a)); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=INF;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(min(a,X.a)); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X(min(p[c].a,lazy[c].a));
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> ar; 
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST1() {N=0LL;}
    ST1(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,arr.size()) {SV X(arr[i]); ar.pb(X);} 
        REP(i,arr.size(),N) {ar.pb(neuts);}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,N) {p.pb(ar[i]); range[i+N]=mp(i,i);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        p[c]=upval(c);
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
        if(2*c>=N) 
        {
            p[2*c]=upval(2*c); p[2*c+1]=upval(2*c+1);
            ar[2*c-N]=p[2*c];
            ar[2*c+1-N]=p[2*c+1];
            lazy[2*c]=neutl; lazy[2*c+1]=neutl;
        }
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b,1)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b,1,0,S.N-1)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            if(c>=N) {p[c]=upval(c); lazy[c]=neutl; ar[c-N]=p[c];}
            return;
        }
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

class ST2
{
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=0LL;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS(max(a,X.a)); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS(max(a,X.a)); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X(max(p[c].a,lazy[c].a));
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> ar; 
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST2() {N=0LL;}
    ST2(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,arr.size()) {SV X(arr[i]); ar.pb(X);} 
        REP(i,arr.size(),N) {ar.pb(neuts);}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,N) {p.pb(ar[i]); range[i+N]=mp(i,i);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        p[c]=upval(c);
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
        if(2*c>=N) 
        {
            p[2*c]=upval(2*c); p[2*c+1]=upval(2*c+1);
            ar[2*c-N]=p[2*c];
            ar[2*c+1-N]=p[2*c+1];
            lazy[2*c]=neutl; lazy[2*c+1]=neutl;
        }
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b,1)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b,1,0,S.N-1)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            if(c>=N) {p[c]=upval(c); lazy[c]=neutl; ar[c-N]=p[c];}
            return;
        }
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    if(k<=5000 && n<=10000)
    {
        REP(i,0,n) {finalHeight[i]=0;}
        REP(i,0,k)
        {
            REP(j,left[i],right[i]+1) 
            {
                if(op[i]==1) {finalHeight[j]=max(finalHeight[j],height[i]);}
                else {finalHeight[j]=min(finalHeight[j],height[i]);}
            }
        }
        return;   
    }
    vector<ll> init; REP(i,0,n) {init.pb(0);}
    ST2 S(init);
    ll ind=0LL;
    while(op[ind]==1)
    {
        S.update(height[ind],left[ind],right[ind]);
        ind++;
    }
    vector<ll> cur_state; REP(i,0,n) {cur_state.pb(S.query(i,i).a);}
    ST1 T(cur_state);
    while(ind<k)
    {
        T.update(height[ind],left[ind],right[ind]);
        ind++;
    }
    REP(i,0,n) {finalHeight[i]=T.query(i,i).a;}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 23 ms 632 KB Output is correct
5 Correct 23 ms 504 KB Output is correct
6 Correct 23 ms 476 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 170 ms 8184 KB Output is correct
3 Incorrect 206 ms 9372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 23 ms 512 KB Output is correct
6 Correct 23 ms 512 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 171 ms 8184 KB Output is correct
9 Incorrect 209 ms 9500 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 24 ms 504 KB Output is correct
6 Correct 23 ms 512 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 169 ms 8176 KB Output is correct
9 Incorrect 209 ms 9372 KB Output isn't correct
10 Halted 0 ms 0 KB -