oj.uz

Submission #275035

# Submission time Handle Problem Language Result Execution time Memory
275035 2020-08-20T04:07:35 Z Masterdan Wall (IOI14_wall) C++14
24 / 100
 483 ms 21128 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define MAX 1e9+7
#define MIN -1
#define  F  first
#define S  second
#define pb push_back
#define mk  make_pair
#define all(a)  a.begin (), a.end ()
#define mem(a, c) memset(a, c, sizeof(a))
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
const int N=1e5+10;
int tree[N*4];
void upd(int node, int in, int fin, int l, int r, int val, int sw){
    //cout<<node<<" "<<in<<" "<<fin<<endl;
    if(in>r || fin<l )return;
    if(in>=l && fin<=r){
        if(sw==1){
            tree[node]=max(tree[node], val);

        }else{
            tree[node]=min(tree[node], val);
        }
        return;
    }
    int mid=(in+fin)/2;
    upd(2*node+1, in, mid, l, r, val, sw);
    upd(2*node+2, mid+1, fin, l, r, val, sw);
}
int query(int node, int in, int fin, int pos, int val, int sw){
    //cout<<node<<" "<<in<<" "<<fin<<endl;
    //cout<<val<<endl;
    if(pos>fin || pos<in){
        if(sw==1)return 0;
        else return MAX;
    }
    if(in==fin){
        if(sw==1)return max(val, tree[node]);
        else return min(val, tree[node]);
    }
    if(sw==1)val=max(val, tree[node]);
    else val=min(val, tree[node]);
    int mid=(in+fin)/2;
    if(sw==1)return max(query(2*node+1, in, mid, pos, val, sw), query(2*node+2, mid+1, fin, pos, val, sw));
    else return min(query(2*node+1, in, mid, pos, val, sw), query(2*node+2, mid+1, fin, pos, val, sw));
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int finalHeight[]){
    mem(tree, 0);
    int c=0;
    for(int i=0;i<k;i++){
        if(op[i]==2)break;
        else c++;
    }
    for(int i=0;i<c;i++){
        upd(0, 0, n-1, l[i], r[i], h[i], 1);
    }
    vi v;
    for(int i=0;i<n;i++){
        v.pb(query(0, 0, n-1, i, 0, 1));
        //if(finalHeight[i]==MAX)finalHeight[i]=0;
    }
 //   for(int i=0;i<n;i++)cout<<v[i]<<" ";
   // cout<<endl;
    for(int i=0;i<=4*N;i++)tree[i]=MAX;
    for(int i=0;i<n;i++){
        upd(0, 0, n-1, i, i, v[i], 2);
    }
    //for(int i=0;i<=50;i++)cout<<tree[i]<<" ";
    //cout<<endl;
    for(int i=c;i<k;i++){
        upd(0, 0, n-1, l[i], r[i], h[i], 2);
    }
   // for(int i=0;i<50;i++)cout<<tree[i]<<" ";
   // cout<<endl;
    for(int i=0;i<n;i++){
        finalHeight[i]=query(0, 0,n-1, i, MAX, 2);
    }
}/*
int lefi[N*5], righi[N*5], op[N*5], height[N*5], finalHeight[N*5];
int main()
{
  int n, k;
  ifstream I1("entrada.txt");
  ifstream I2("salida.txt");
  while(I1>>n>>k){
    cout<<n<<" "<<k<<endl;
    for(int i=0;i<k;i++){
        I1>>op[i]>>lefi[i]>>righi[i]>>height[i];
    }
  //  cout<<2<<endl;
    buildWall(n, k, op, lefi, righi, height, finalHeight);
    vi ans;
    for(int i=0;i<n;i++){
        int x;
        I2>>x;
        ans.pb(x);
    }
    for (int j = 0; j < n; j++) cout<<finalHeight[j]<<" ";
    cout<<endl;
    int sw=-1;
    vi mals;
    for(int i=0;i<n;i++)if(ans[i]!=finalHeight[i]){
        mals.pb(i);
        sw=1;
    }
    if(sw==-1)cout<<"BIEN"<<endl;
    else {
        for(int i=0;i<mals.size ();i++)cout<<mals[i]<<" ";
        cout<<endl;
    }
    }
}
*/

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:69:35: warning: iteration 400040 invokes undefined behavior [-Waggressive-loop-optimizations]
   69 |     for(int i=0;i<=4*N;i++)tree[i]=MAX;
      |                                   ^
wall.cpp:69:18: note: within this loop
   69 |     for(int i=0;i<=4*N;i++)tree[i]=MAX;
      |                 ~^~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Incorrect 4 ms 2048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 194 ms 10616 KB Output is correct
3 Correct 168 ms 6320 KB Output is correct
4 Correct 483 ms 11672 KB Output is correct
5 Correct 362 ms 21128 KB Output is correct
6 Correct 370 ms 19560 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Incorrect 4 ms 2048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1920 KB Output is correct
2 Incorrect 4 ms 2048 KB Output isn't correct
3 Halted 0 ms 0 KB -