oj.uz

Submission #204579

# Submission time Handle Problem Language Result Execution time Memory
204579 2020-02-26T10:43:36 Z awlintqaa Wall (IOI14_wall) C++14
32 / 100
 1192 ms 40072 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 200
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf= 4e18;
const ld pai=acos(-1);
#include "wall.h"
int n,q;
vi MX[100009][2],MN[100009][2];
int mx[100009],mn[100009];
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
        n=N,q=k;
        for(int i=0;i<n;i++)finalHeight[i]=0;
        if(n<=1e4 && q<=5e3){
                for(int i=0;i<q;i++){
                        int t=op[i];
                        int l=left[i];
                        int r=right[i];
                        int h=height[i];
                        for(int j=l;j<=r;j++){
                                if(t==1){
                                        finalHeight[j]=max(finalHeight[j],h);
                                }
                                if(t==2){
                                        finalHeight[j]=min(finalHeight[j],h);
                                }
                        }
                }
                return ;
        }
        for(int i=0;i<q;i++){
                int t=op[i];
                int l=left[i];
                int r=right[i];
                int h=height[i];
                if(t==1){
                        MX[l][0].pb(h);
                        MX[r][1].pb(h);
                }
                if(t==2){
                        MN[l][0].pb(h);
                        MN[r][1].pb(h);
                }
        }
        mset<int>s;
        for(int i=0;i<n;i++)mn[i]=1e9;
        for(int i=0;i<n;i++){
                for(auto u:MX[i][0])s.ins(u);
                if(s.size())mx[i]=*s.rbegin();
                for(auto u:MX[i][1])s.era(s.find(u));
        }
        s.clear();
        for(int i=0;i<n;i++){
                for(auto u:MN[i][0])s.ins(u);
                if(s.size())mn[i]=*s.begin();
                for(auto u:MN[i][1])s.era(s.find(u));
        }
        for(int i=0;i<n;i++){
                if(mn[i]<mx[i]){
                        finalHeight[i]=mn[i];
                }
                else{
                        finalHeight[i]=mx[i];
                }
        }
        return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 13 ms 9720 KB Output is correct
3 Correct 12 ms 9720 KB Output is correct
4 Correct 37 ms 9872 KB Output is correct
5 Correct 34 ms 9848 KB Output is correct
6 Correct 29 ms 9848 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 879 ms 39628 KB Output is correct
3 Correct 299 ms 20984 KB Output is correct
4 Correct 1192 ms 39924 KB Output is correct
5 Correct 319 ms 28280 KB Output is correct
6 Correct 276 ms 27984 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 13 ms 9720 KB Output is correct
3 Correct 12 ms 9976 KB Output is correct
4 Correct 29 ms 9848 KB Output is correct
5 Correct 30 ms 9848 KB Output is correct
6 Correct 30 ms 9848 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 781 ms 39624 KB Output is correct
9 Correct 279 ms 20988 KB Output is correct
10 Correct 1087 ms 40072 KB Output is correct
11 Correct 299 ms 28024 KB Output is correct
12 Correct 277 ms 28024 KB Output is correct
13 Correct 11 ms 9720 KB Output is correct
14 Incorrect 689 ms 33188 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9724 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 15 ms 9720 KB Output is correct
4 Correct 31 ms 9976 KB Output is correct
5 Correct 29 ms 9848 KB Output is correct
6 Correct 31 ms 9848 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 812 ms 39644 KB Output is correct
9 Correct 278 ms 20984 KB Output is correct
10 Correct 1074 ms 40056 KB Output is correct
11 Correct 308 ms 28120 KB Output is correct
12 Correct 281 ms 28024 KB Output is correct
13 Correct 11 ms 9720 KB Output is correct
14 Incorrect 685 ms 33316 KB Output isn't correct
15 Halted 0 ms 0 KB -