oj.uz

Submission #986743

# Submission time Handle Problem Language Result Execution time Memory
986743 2024-05-21T07:19:00 Z emad234 Wall (IOI14_wall) C++17
0 / 100
 122 ms 262144 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 = 8e6 + 5;
const int mod = 1e9 + 7;
const int inf = INT_MAX;
using namespace std;
struct range{
    int l,r,h,op;
    friend bool operator<(range a, range b){
        return a.l < b.l;
    }
};
struct event{
    int ty,op,id,val;
};
queue<event>q[mxN];
pii seg[mxN];
int N,s,e;
pii combine(pii a,pii b){
    pii c;
    c.F = min(max(b.F,a.F),b.S);
    c.S = max(min(a.S,b.S),c.F);
    return c;
}
pii query(int l,int r,int ind){
    if(l > e || r < s) return {0,inf};
    if(l >= s && r <= e) return seg[ind];
    int md = (l + r) / 2;
    return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void update(int ind,pii val){
    ind += N;
    seg[ind] = 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<<" , "<<seg[i].S<<" } ";
        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[]){
    vector<range>v;
    for(int i = 0;i < k;i++) v.push_back({left[i],right[i],height[i],op[i]});
    sort(v.begin(),v.end());
    N = exp2(ceil(log2(n)));
    for(int i = 1;i <= N * 2;i++){
        seg[i] = {0,inf};
    }
    for(int i = 0;i < v.size();i++){
        auto x = v[i];
        q[x.l].push({1,x.op,i,x.h});
        q[x.r + 1].push({-1,x.op,i,x.h});
    }
    s = 1,e = n;
    for(int i = 0;i < n;i++){
        while(q[i].size()){
            auto u = q[i].front();
            q[i].pop();
            if(u.ty == -1){
                update(u.id,{0,inf});
            }else{
                if(u.op == 1)
                    update(u.id,{u.val,inf});
                else
                    update(u.id,{0,u.val});
            }
        }
        // printseg();
        finalHeight[i] = query(1,N,1).F;
    }


}

Compilation message

wall.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 0;i < v.size();i++){
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -