Submission #274982

#	Time	Username	Problem	Language	Result	Execution time	Memory
274982		Masterdan	Wall (IOI14_wall)	C++14	0 / 100	452 ms	11608 KiB

wall

#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<=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 main()
{
  int n;
  int k;
  int i, j;
  int status = 0;
  status = scanf("%d%d", &n, &k);
  assert(status == 2);
  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++) cout<<finalHeight[j]<<endl;

}
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39