제출 #986896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986896		Rifal	벽 (IOI14_wall)	C++14	24 / 100	446 ms	48516 KiB

wall

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
const int N = 5e5 + 5;
pair<int,int> seg[N*4];
struct wall {
    int h, ty, ord;
};
pair<int,int> mer(pair<int,int> a, pair<int,int> b) {
    if(a.first == 0 && a.second == INF && b.first == 0 && b.second == INF) {
       // cout << 'a' << endl;
        return {0,INF};
    }
    else if(a.first != 0 && a.second == INF && b.first == 0 && b.second == INF)  {
       // cout << 'b' << endl;
        return {a.first,INF};
    }
    else if(a.first == 0 && a.second == INF && b.first != 0 && b.second == INF)  {
      //  cout << 'c' << endl;
        return {b.first,INF};
    }
    else if(a.first == 0 && a.second == INF && b.first == 0 && b.second != INF)  {
      //  cout << 'd' << endl;
        return {0,b.second};
    }
    else if(a.first == 0 && a.second != INF && b.first == 0 && b.second == INF)  {
      //  cout << 'e' << endl;
        return {0,a.second};
    }
    else if(a.second == INF && b.second == INF && a.first != 0 && b.first != 0) {
     //   cout << 't' << endl;
        return {max(a.first,b.first),INF};
    }
    else if(a.first == 0 && b.first == 0 && a.second != INF && b.second != INF) {
       // cout << 'o' << endl;
        return {0,min(a.second,b.second)};
    }
    else if(a.first == 0 && a.second != INF && b.first != 0 && b.second == INF) {
     //   cout << 'p' << endl;
        if(a.second > b.first) return {b.first,a.second};
        else return {b.first,b.first};
    }
    else if(a.first != 0 && a.second == INF && b.first == 0 && b.second != INF) {
    //    cout << 's' << endl;
       if(b.second > a.first) return {a.first,b.second};
       else return {b.second,b.second};
    }
    else if(b.first == b.second) {
      //  cout << 'm' << endl;
        return {b.first,b.second};
    }
    else if(a.first == a.second) {
     //   cout << 'y' << endl;
        if(b.first > a.first) {
            return {max(a.first,b.first),max(a.first,b.first)};
        }
        else if(b.second < a.second) {
            return {min(a.second,b.second),min(a.second,b.second)};
        }
        else {
            return {a.first,a.second};
        }
    }
    else if(a.first != 0 && a.second != 0) {
     //   cout << 'q' << endl;
        if(a.second < b.first) {
            return {b.first,b.first};
        }
        else if(a.first > b.second) {
            return {b.second,b.second};
        }
        else {
            return {max(a.first,b.first),min(a.second,b.second)};
        }
    }
    return {0,INF};
}
void Build(int x, int l, int r) {
    if(l == r) {
        seg[x].first = 0;
        seg[x].second = INF;
    }
    else {
        int mid = (l+r)/2;
        Build(x*2,l,mid);
        Build(x*2+1,mid+1,r);
        seg[x].first = 0;
        seg[x].second = INF;
    }
}
void Update(int x, int l, int r, int pos, int ty, int val) {
    if(l == r) {
        if(val < 0) {
          //  cout << "aa" << endl;
            if(ty == 1) seg[x].first = 0;
            else seg[x].second = INF;
        }
        else {
          //  cout << "bb" << endl;
            if(ty == 1) seg[x].first = val;
            else seg[x].second = val;
        }
      //  cout << seg[x].first  << ' ' << seg[x].second << endl;
    }
    else {
        int mid = (l+r)/2;
        if(pos <= mid) Update(x*2,l,mid,pos,ty,val);
        else Update(x*2+1,mid+1,r,pos,ty,val);
        pair<int,int> pp = mer(seg[x*2],seg[x*2+1]);
    //    cout << l << ' ' << r << 'k' << endl;
      //  cout << pp.first << ' ' << pp.second << 'a' << endl;
        seg[x] = pp;
    }
}
vector<wall> v[N];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for(int i = 0; i < k; i++) {
        if(op[i] == 1) {
            wall cur;
            cur.h = height[i]+1;
            cur.ty = 1;
            cur.ord = i+1;
            v[left[i]].push_back(cur);
            cur.h *= -1;
            v[right[i]+1].push_back(cur);
        }
        else {
            wall cur;
            cur.h = height[i]+1;
            cur.ty = 2;
            cur.ord = i+1;
            v[left[i]].push_back(cur);
            cur.h *= -1;
            v[right[i]+1].push_back(cur);
        }
     }
     for(int i = 0; i < n; i++) finalHeight[i] = 1;
     Build(1,1,k+1);
     for(int i = 0; i < n; i++) {
        for(auto j : v[i]) {
           // cout << "JJJJJJJJJJJJJ" << endl;
           // cout << j.ord << ' ' << j.h << 'p' << endl;
            Update(1,1,k+1,j.ord,j.ty,j.h);
        }
        if(finalHeight[i] < seg[1].first) finalHeight[i] = seg[1].first;
        if(finalHeight[i] > seg[1].second) finalHeight[i] = seg[1].second;
     }
     for(int i = 0; i < n; i++) finalHeight[i]--;
}

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