oj.uz

Submission #605171

# Submission time Handle Problem Language Result Execution time Memory
605171 2022-07-25T13:38:56 Z HediChehaidar Wall (IOI14_wall) C++17
100 / 100
 1553 ms 96428 KB 
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = 1e9 + 7;//998244353 ;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

int st[(int)5e6 + 10];
int lazy[(int)5e6 + 10];
int mx[(int)5e6 + 10];
int mn[(int)5e6 + 10];
void update(int pos , int l , int r , int i , int j , int t, int w){
    if(lazy[pos] != -1){
        mn[pos] = mx[pos] = st[pos] = lazy[pos];
        if(l != r) {
            lazy[2 * pos + 1] = lazy[pos];
            lazy[2 * pos + 2] = lazy[pos];
        }
        lazy[pos] = -1;
    }
    if(i > r || j < l) return ;
    if( (t == 1 && mn[pos] >= w) || (t == 2 && mx[pos] <= w) ) return ;
    if(i <= l && j >= r &&  ((t == 1 && mx[pos] < w) || (t == 2 && mn[pos] > w) ) ) {
        st[pos] = mn[pos] = mx[pos] = w;
        if(l != r){
            lazy[2 * pos + 1] = w;
            lazy[2 * pos + 2] = w;
        }
        return ;
    }
    update(2 * pos  + 1 , l , (l+r) / 2 , i , j , t , w); update(2 * pos + 2 , (l+r) / 2 + 1 , r , i , j , t , w);
    mn[pos] = min(mn[2 * pos + 1] , mn[2 * pos + 2]); mx[pos] = max(mx[2 * pos + 1] , mx[2 * pos + 2]);
}
int rq(int pos , int l , int r , int i ){
    if(lazy[pos] != -1){
        if(l == r) st[pos] = lazy[pos];
        if(l != r) {
            lazy[2 * pos + 1] = lazy[pos];
            lazy[2 * pos + 2] = lazy[pos];
        }
        lazy[pos] = -1;
    }
    if(i > r || i  < l) return -1;
    if(l == r) return st[pos];
    int p1 = rq(2 * pos + 1 , l , (l+r) / 2 , i) , p2 = rq(2 * pos + 2 , (l+r)/ 2 + 1 , r, i);
    if(p1 == -1) return p2;
    return p1;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    memset(lazy , -1 , sizeof lazy);
    for(int i = 0 ; i < k ; i++) update(0 , 0 , n - 1 , left[i] , right[i] , op[i] , height[i]);
    for(int i = 0 ; i < n ; i++) finalHeight[i] = rq(0 , 0 , n - 1 , i);
    //for(int i = 0 ; i < n ; i++) cout << finalHeight[i] << " "; cout << "\n";
    return ;
}
int op[101];
int l[101];
int r[101];
int height[101];
int v[101];
/*int main(){
    //ifstream fin ("testing.txt");
    //ofstream fout ("output.txt");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int  n , k; cin>>n>>k;
    for(int i = 0 ; i < k ; i++) cin>>op[i]>>l[i]>>r[i]>>height[i];
    buildWall(n , k , op , l , r , height , v);
    //for(auto c : v) cout << c << " "; cout << "\n";
    return 0;
}*/
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19796 KB Output is correct
2 Correct 10 ms 19924 KB Output is correct
3 Correct 9 ms 19924 KB Output is correct
4 Correct 14 ms 20388 KB Output is correct
5 Correct 13 ms 20436 KB Output is correct
6 Correct 14 ms 20436 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 133 ms 27664 KB Output is correct
3 Correct 84 ms 23852 KB Output is correct
4 Correct 175 ms 30468 KB Output is correct
5 Correct 177 ms 29720 KB Output is correct
6 Correct 206 ms 29700 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19796 KB Output is correct
2 Correct 10 ms 19944 KB Output is correct
3 Correct 9 ms 19924 KB Output is correct
4 Correct 14 ms 20436 KB Output is correct
5 Correct 14 ms 20340 KB Output is correct
6 Correct 13 ms 20388 KB Output is correct
7 Correct 10 ms 19836 KB Output is correct
8 Correct 132 ms 27704 KB Output is correct
9 Correct 89 ms 23832 KB Output is correct
10 Correct 183 ms 30552 KB Output is correct
11 Correct 201 ms 29704 KB Output is correct
12 Correct 207 ms 29740 KB Output is correct
13 Correct 12 ms 19796 KB Output is correct
14 Correct 137 ms 27656 KB Output is correct
15 Correct 36 ms 21736 KB Output is correct
16 Correct 444 ms 41252 KB Output is correct
17 Correct 324 ms 40640 KB Output is correct
18 Correct 311 ms 40624 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 12 ms 19880 KB Output is correct
3 Correct 9 ms 19924 KB Output is correct
4 Correct 13 ms 20436 KB Output is correct
5 Correct 13 ms 20376 KB Output is correct
6 Correct 14 ms 20340 KB Output is correct
7 Correct 8 ms 19796 KB Output is correct
8 Correct 127 ms 27684 KB Output is correct
9 Correct 86 ms 23852 KB Output is correct
10 Correct 239 ms 30536 KB Output is correct
11 Correct 177 ms 29772 KB Output is correct
12 Correct 207 ms 29716 KB Output is correct
13 Correct 10 ms 19796 KB Output is correct
14 Correct 192 ms 27636 KB Output is correct
15 Correct 35 ms 21816 KB Output is correct
16 Correct 574 ms 41200 KB Output is correct
17 Correct 346 ms 40624 KB Output is correct
18 Correct 368 ms 40624 KB Output is correct
19 Correct 1222 ms 96392 KB Output is correct
20 Correct 1175 ms 93860 KB Output is correct
21 Correct 1268 ms 96384 KB Output is correct
22 Correct 1158 ms 93968 KB Output is correct
23 Correct 1160 ms 93936 KB Output is correct
24 Correct 1553 ms 93888 KB Output is correct
25 Correct 1163 ms 93944 KB Output is correct
26 Correct 1219 ms 96428 KB Output is correct
27 Correct 1103 ms 96380 KB Output is correct
28 Correct 1022 ms 93848 KB Output is correct
29 Correct 1094 ms 93852 KB Output is correct
30 Correct 1049 ms 93844 KB Output is correct