oj.uz

Submission #986850

# Submission time Handle Problem Language Result Execution time Memory
986850 2024-05-21T11:19:40 Z emad234 Wall (IOI14_wall) C++17
0 / 100
 149 ms 60696 KB 
#pragma once
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = (1 << 20);
const int mod = 1e9 + 7;
const int inf = INT_MAX;
using namespace std;
struct event{
    int ty,op,id,val;
};
vector<event>q[mxN];
pii seg[mxN];
int N,s,e;
pii combine(pii a,pii b){
    pii c;
    c.F = min(a.F,b.S);
    c.F = max(c.F,b.F);
    c.S = min(a.S,b.S);
    return c;
}
void update(int ind,int id,int val){
    ind += N;
    if(id == 1) seg[ind].F = val;
    else seg[ind].S = val;
    while(ind /= 2) seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
}
void printseg(){
    int ex = 1;
    for(int i = 1;i < N * 2;i++){
        cout<<"{ "<<seg[i].F<<" , ";
        if(seg[i].S == inf) cout<<"inf";
        else cout<<seg[i].S;
        cout<<" } ";
        if(ex * 2 - 1 == i){
            ex *= 2;
            cout<<'\n';
        }
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = exp2(ceil(log2(n)));
    for(int i = 1;i <= N * 2;i++){
        seg[i] = {0,inf};
    }
    for(int i = 0;i < k;i++){
        q[left[i]].push_back({1,op[i],i,height[i]});
        q[right[i] + 1].push_back({-1,op[i],i,height[i]});
    }
    s = 1,e = n;
    for(int i = 0;i < n;i++){
        while(q[i].size()){
            auto u = q[i].back();
            q[i].pop_back();
            if(u.ty == -1){
                if(u.op == 1)
                    update(u.id,1, 0);
                if(u.op == 2)
                    update(u.id,2, inf);
            }else{
                if(u.op == 1)
                    update(u.id,1, u.val);
                else
                    update(u.id,2, u.val);
            }
        }
        finalHeight[i] = seg[1].F;
    }
}

Compilation message

wall.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26936 KB Output is correct
2 Incorrect 8 ms 27228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Incorrect 149 ms 60696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26716 KB Output is correct
2 Incorrect 8 ms 27228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Incorrect 8 ms 27208 KB Output isn't correct
3 Halted 0 ms 0 KB -