oj.uz

Submission #1023556

# Submission time Handle Problem Language Result Execution time Memory
1023556 2024-07-15T02:25:14 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 584 ms 85956 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define fls cout.flush()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using mii = map<int,int>;
using lld = long double;
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
const int mod = 1e9+7;
bool umax(int &a, int b){if(b >a){a = b; return 1;} return 0;}
bool umin(int &a, int b){if(b <a){a = b; return 1;} return 0;}
struct node{int mn,mx,pr;};
node st[8000008];
void pro(int nodo,int l, int r ){
    if(st[nodo].pr == 0 || l == r) return;
    int mid =(l+r)/2;st[nodo].pr = 0;
    umax(st[nodo*2].mn, st[nodo].mn);umin(st[nodo*2].mn,st[nodo].mx);
    umin(st[nodo*2].mx, st[nodo].mx);umax(st[nodo*2].mx,st[nodo].mn);
    umax(st[nodo*2+1].mn, st[nodo].mn);umin(st[nodo*2+1].mn,st[nodo].mx);
    umin(st[nodo*2+1].mx, st[nodo].mx);umax(st[nodo*2+1].mx,st[nodo].mn);
    st[nodo*2].pr = -1;st[nodo*2+1].pr = -1;
}
void update(int nodo, int l, int r , int i, int j, int op, int val){
    pro(nodo,l,r);
    // cout << nodo << " " << l << " " << r << endl;
    if(i > r || j < l)return;
    if(l >= i and r <= j){// rango completo
        if(op==1){
            umax(st[nodo].mn, val); umax(st[nodo].mx, val);
        }else{
            umin(st[nodo].mn, val); umin(st[nodo].mx, val);
        }
        st[nodo].pr = -1;
        pro(nodo,l,r);return;
    }
    update(nodo*2,l,(l+r)/2,i,j,op,val);
    update(nodo*2+1,(l+r)/2 +1, r, i,j,op,val);
    st[nodo].mn = min(st[nodo*2].mn , st[nodo*2+1].mn);
    st[nodo].mx = max(st[nodo*2].mx , st[nodo*2+1].mx);
}
int query(int nodo, int l, int r, int idx){
    pro(nodo,l,r);
    if(l == r)return st[nodo].mn;
    int mid = (l+r)/2;
    if(idx <= mid) return query(nodo*2,l,mid,idx);
    return query(nodo*2+1,mid+1,r,idx);
}
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) update(1,0,n-1,left[i], right[i], 1, height[i]);
        else update(1,0,n-1,left[i], right[i], 0, height[i]);
    }
    for(int i = 0; i < n; i++)
        finalHeight[i] = query(1,0,n-1, i);
    return;
}

Compilation message

wall.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
wall.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
wall.cpp: In function 'void pro(int, int, int)':
wall.cpp:38:9: warning: unused variable 'mid' [-Wunused-variable]
   38 |     int mid =(l+r)/2;st[nodo].pr = 0;
      |         ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1060 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 968 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 84 ms 13912 KB Output is correct
3 Correct 152 ms 8304 KB Output is correct
4 Correct 434 ms 21356 KB Output is correct
5 Correct 199 ms 22612 KB Output is correct
6 Correct 175 ms 20820 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1028 KB Output is correct
5 Correct 3 ms 1060 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 14296 KB Output is correct
9 Correct 150 ms 8280 KB Output is correct
10 Correct 445 ms 21472 KB Output is correct
11 Correct 223 ms 22352 KB Output is correct
12 Correct 187 ms 20820 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 100 ms 14076 KB Output is correct
15 Correct 29 ms 2388 KB Output is correct
16 Correct 500 ms 21588 KB Output is correct
17 Correct 231 ms 21152 KB Output is correct
18 Correct 202 ms 21036 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 3 ms 1044 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13908 KB Output is correct
9 Correct 147 ms 8276 KB Output is correct
10 Correct 423 ms 21328 KB Output is correct
11 Correct 168 ms 22352 KB Output is correct
12 Correct 193 ms 20820 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 13916 KB Output is correct
15 Correct 28 ms 2388 KB Output is correct
16 Correct 521 ms 21724 KB Output is correct
17 Correct 189 ms 21072 KB Output is correct
18 Correct 176 ms 21072 KB Output is correct
19 Correct 528 ms 85844 KB Output is correct
20 Correct 550 ms 83540 KB Output is correct
21 Correct 489 ms 85844 KB Output is correct
22 Correct 514 ms 83532 KB Output is correct
23 Correct 520 ms 83488 KB Output is correct
24 Correct 584 ms 83560 KB Output is correct
25 Correct 538 ms 83540 KB Output is correct
26 Correct 576 ms 85956 KB Output is correct
27 Correct 554 ms 85840 KB Output is correct
28 Correct 568 ms 83540 KB Output is correct
29 Correct 524 ms 83384 KB Output is correct
30 Correct 532 ms 83520 KB Output is correct