oj.uz

답안 #254171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254171 2020-07-29T12:44:35 Z PedroBigMan 벽 (IOI14_wall) C++14
32 / 100
 745 ms 32464 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 50000000LL
#define EPS 0.00000001
#define pi 3.14159

class ST1
{
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=INF;}
        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

# 결과 실행 시간 메모리 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 512 KB Output is correct
6 Correct 24 ms 504 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 170 ms 8184 KB Output is correct
3 Correct 212 ms 9372 KB Output is correct
4 Correct 745 ms 31820 KB Output is correct
5 Correct 406 ms 32336 KB Output is correct
6 Correct 379 ms 32212 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 24 ms 512 KB Output is correct
5 Correct 23 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 8168 KB Output is correct
9 Correct 213 ms 9500 KB Output is correct
10 Correct 674 ms 31956 KB Output is correct
11 Correct 385 ms 32460 KB Output is correct
12 Correct 367 ms 32340 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Incorrect 173 ms 8696 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 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 23 ms 512 KB Output is correct
6 Correct 23 ms 504 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 171 ms 8184 KB Output is correct
9 Correct 215 ms 9372 KB Output is correct
10 Correct 699 ms 31888 KB Output is correct
11 Correct 402 ms 32336 KB Output is correct
12 Correct 381 ms 32464 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Incorrect 169 ms 8696 KB Output isn't correct
15 Halted 0 ms 0 KB -