답안 #672440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672440	2022-12-16T07:31:12 Z	bLIC	벽 (IOI14_wall)	C++17	100 / 100	662 ms	135220 KB

wall

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// typedef tree<int,null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 998244353;
const ll INFLL = 1e18;
const int INF = 1e9;
const int maxN = 2e5+6;
const int maxK = 10;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}


#define gbit(x, i) (((1<<i)&(x))!=0)

template <typename T>
class MINT{
    T x;
    public:
    static T MOD;
    MINT(T _x){x = (_x%MOD+MOD)%MOD;}
    MINT():MINT(0){}
    explicit operator ll(){return x;}
    friend MINT operator+(const MINT& m1, const MINT& m2){return MINT((m1.x + m2.x)%MOD);};
    friend MINT operator-(const MINT& m1, const MINT& m2){return MINT(((m1.x - m2.x)%MOD + MOD)%MOD);};
    friend MINT operator*(const MINT& m1, const MINT& m2){return MINT((m1.x * m2.x)%MOD);};
    MINT& operator+=(const MINT& m2){return *this = *this + m2;};
    MINT& operator-=(const MINT& m2){return *this = *this - m2;};
    MINT& operator*=(const MINT& m2){return *this = *this * m2;};
    friend bool operator==(const MINT& m1, const MINT& m2){return m1.x==m2.x;};
    friend istream& operator>>(istream& in, const MINT& m){in>>m.x;return in;};
    friend ostream& operator<<(ostream& out, const MINT& m){out<<m.x;return out;};
};
template <typename T>
T MINT<T>::MOD = 998244353;

typedef MINT<ll> mll;

typedef pair<mll, mll> pmll;

#define lt(x) ((x)<<1)
#define rt(x) ((x)<<1|1)


struct Node {
    ll h, mx, mn;
    Node(ll x):h(x), mx(INF), mn(0){}
    Node():Node(0){}
};

vector<Node> tree;
int n;
void init(int _n){
    n = 1;
    while(n<_n) n<<=1;
    tree.assign(2*n, Node());
}

void opt(Node& par, Node& chi){
    chi.mx = min(chi.mx, par.mx);
    chi.mx = max(chi.mx, par.mn);
    chi.mn = max(chi.mn, par.mn);
    chi.mn = min(chi.mn, par.mx);
}

void pushdown(int x){
    if (x>=n) return;
    opt(tree[x], tree[lt(x)]);
    opt(tree[x], tree[rt(x)]);
    tree[x].mn = 0;
    tree[x].mx = INF;
}

// void build(vector<ll>& v){
//     for (int i = 0;i<sz(v);i++) tree[i+n] = v[i];
//     for (int i = n-1;i>0;i--) pushup(i);
// }
void updatemx(int l, int r, int x, int lx, int rx, ll val){
    if (l<=lx && rx<=r) {
        tree[x].mx = min(tree[x].mx, val);
        tree[x].mn = min(tree[x].mn, val);
        return;
    }
    if (l>=rx || r<=lx) return;
    int m = (lx+rx)/2;
    pushdown(x);
    updatemx(l, r, lt(x), lx, m, val);
    updatemx(l, r, rt(x), m, rx, val);
    // pushup(x);
}

void updatemx(int l, int r, ll val){
    updatemx(l, r, 1, 0, n, val);
}
void updatemn(int l, int r, int x, int lx, int rx, ll val){
    if (l<=lx && rx<=r) {
        tree[x].mx = max(tree[x].mx, val);
        tree[x].mn = max(tree[x].mn, val);
        return;
    }
    if (l>=rx || r<=lx) return;
    int m = (lx+rx)/2;
    pushdown(x);
    updatemn(l, r, lt(x), lx, m, val);
    updatemn(l, r, rt(x), m, rx, val);
    // pushup(x);
}

void updatemn(int l, int r, ll val){
    updatemn(l, r, 1, 0, n, val);
}

// ll querysm(int l, int r, int x, int lx, int rx){
//     if (l<=lx && rx<=r) return tree[x].s;
//     else if (l>=rx || r<=lx) return 0;
//     else {
//         int m = (lx+rx)/2;
//         pushdown(x, lx, m, rx);
//         return (querysm(l, r, lt(x), lx, m)+querysm(l,r , rt(x), m, rx));
//     }
// }

// ll querysm(int l, int r){
//     return querysm(l, r, 1, 0, n);
// }

// ll querymin(int l, int r, int x, int lx, int rx){
//     if (l<=lx && rx<=r) return tree[x].m;
//     else if (l>=rx || r<=lx) return -INFLL;
//     else {
//         int m = (lx+rx)/2;
//         pushdown(x, lx, m, rx);
//         return max(querymin(l, r, lt(x), lx, m), querymin(l, r, rt(x), m, rx));
//     }
// }

// ll querymin(int l, int r){
//     return querymin(l, r, 1, 0, n);
// }

template <class T>
istream& operator>>(istream& in, vector<T>& v){
    for (T& x:v) in>>x;
    return in;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    init(n);
    vi h(n);
    // for (int i = 0;i<n;i++) h[i] = height[i];
    // build(h);
    for (int i = 0;i<k;i++){
        if (op[i]==1) updatemn(left[i], right[i]+1, height[i]);
        else updatemx(left[i], right[i]+1, height[i]);
    }
    for (int i = 1;i<::n;i++) pushdown(i);
    for (int i = 0;i<n;i++) finalHeight[i] = min(tree[i+::n].mn, tree[i+::n].mx);
}


// void solve(){
    
   
// }


// int main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cout.tie(nullptr);
// // #define _DEBUG
// #ifdef _DEBUG
// 	freopen("haybales.in", "r", stdin);
// 	freopen("haybales.out", "w", stdout);
// 	int tt = clock();
// #endif
//     int t=1, i = 1;
//     // cin>>t;
//     while(t--){
//         // cout<<"Case #"<<i++<<": ";
//         solve();
//         // cout<<'\n';
//     }
// #ifdef _DEBUG
//     cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
//     tt = clock();
// #endif
// }
// 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++)
//     printf("%d\n", finalHeight[j]);
  
//   return 0;
// }	

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	5 ms	1268 KB	Output is correct
5	Correct	4 ms	1364 KB	Output is correct
6	Correct	5 ms	1364 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	117 ms	8056 KB	Output is correct
3	Correct	150 ms	9136 KB	Output is correct
4	Correct	443 ms	24632 KB	Output is correct
5	Correct	281 ms	25540 KB	Output is correct
6	Correct	259 ms	23864 KB	Output is correct

Subtask #3

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	5 ms	1364 KB	Output is correct
5	Correct	4 ms	1364 KB	Output is correct
6	Correct	5 ms	1364 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	122 ms	13860 KB	Output is correct
9	Correct	141 ms	9036 KB	Output is correct
10	Correct	430 ms	24676 KB	Output is correct
11	Correct	269 ms	25412 KB	Output is correct
12	Correct	263 ms	23852 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	125 ms	13860 KB	Output is correct
15	Correct	24 ms	3020 KB	Output is correct
16	Correct	406 ms	24652 KB	Output is correct
17	Correct	268 ms	24100 KB	Output is correct
18	Correct	260 ms	24048 KB	Output is correct

Subtask #4

39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	5 ms	1364 KB	Output is correct
5	Correct	5 ms	1364 KB	Output is correct
6	Correct	4 ms	1340 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	121 ms	13924 KB	Output is correct
9	Correct	143 ms	8996 KB	Output is correct
10	Correct	437 ms	24692 KB	Output is correct
11	Correct	270 ms	25412 KB	Output is correct
12	Correct	266 ms	23860 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	129 ms	13812 KB	Output is correct
15	Correct	24 ms	3096 KB	Output is correct
16	Correct	404 ms	24688 KB	Output is correct
17	Correct	263 ms	24132 KB	Output is correct
18	Correct	265 ms	24128 KB	Output is correct
19	Correct	636 ms	135152 KB	Output is correct
20	Correct	643 ms	132732 KB	Output is correct
21	Correct	641 ms	135220 KB	Output is correct
22	Correct	630 ms	132764 KB	Output is correct
23	Correct	634 ms	132684 KB	Output is correct
24	Correct	630 ms	132732 KB	Output is correct
25	Correct	646 ms	132648 KB	Output is correct
26	Correct	650 ms	135148 KB	Output is correct
27	Correct	640 ms	135156 KB	Output is correct
28	Correct	662 ms	132648 KB	Output is correct
29	Correct	643 ms	132708 KB	Output is correct
30	Correct	641 ms	132672 KB	Output is correct