oj.uz

Submission #162598

# Submission time Handle Problem Language Result Execution time Memory
162598 2019-11-09T01:54:03 Z 12tqian Wall (IOI14_wall) C++14
100 / 100
 1164 ms 69752 KB 
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const long double PI = 4 * atan((long double) 1);

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef complex<ld> cd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) rbegin(x), rend(x)
#define resz resize
#define ins insert

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}

template<class T> bool ckmin(T& a, const T& b) {
	return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}

void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const int MAX = 2e6 + 5;
const int INF = 1e9 + 5;
const int SZ = (1<<21);
pi seg[2*SZ];
pi lazy[2*SZ];
void comb(pi& a, pi b){
    ckmin(a.s, b.s);
    ckmin(a.f, b.s);
    ckmax(a.f, b.f);
}
void build(){;
    f0r(i, 2*SZ) seg[i] = mp(-INF, INF);
}
void push(int ind){
    if(ind<SZ){
        comb(seg[2*ind], seg[ind]);
        comb(seg[2*ind+1], seg[ind]);
        seg[ind] = mp(-INF, INF);
    }
}
void upd(int l, int r, pi val, int ind = 1, int L = 0, int R = SZ - 1){
    push(ind);
    if(r<L || R<l) return;
    if(l<= L && R<= r){
        comb(seg[ind], val);
        push(ind);
        return;
    }
    int M = (L + R)/2;
    upd(l, r, val, 2*ind, L, M); upd(l, r, val, 2*ind+1, M+1, R);
}

int query(int k, int ind = 1, int L = 0, int R = SZ - 1){
    k += SZ;
    pi res = seg[k];
    k >>= 1;
    while(k>0){
        comb(res, seg[k]);
        k >>= 1;
    }
    int ans = 0;
    ckmin(ans, res.s);
    ckmax(ans, res.f);
    return ans;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build();
    f0r(i, k){
        if(op[i] == 1) upd(left[i], right[i], mp(height[i], INF));
        else upd(left[i], right[i], mp(-INF, height[i]));
    }
    f0r(i, n) {
        finalHeight[i] = query(i);

    }
}

Compilation message

wall.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
wall.cpp: In function 'void io(std::__cxx11::string)':
wall.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33148 KB Output is correct
2 Correct 34 ms 33272 KB Output is correct
3 Correct 31 ms 33144 KB Output is correct
4 Correct 41 ms 33400 KB Output is correct
5 Correct 38 ms 33400 KB Output is correct
6 Correct 37 ms 33528 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33144 KB Output is correct
2 Correct 359 ms 46872 KB Output is correct
3 Correct 331 ms 40440 KB Output is correct
4 Correct 884 ms 51292 KB Output is correct
5 Correct 429 ms 52268 KB Output is correct
6 Correct 396 ms 50680 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33144 KB Output is correct
2 Correct 35 ms 33272 KB Output is correct
3 Correct 33 ms 33272 KB Output is correct
4 Correct 42 ms 33400 KB Output is correct
5 Correct 37 ms 33404 KB Output is correct
6 Correct 37 ms 33400 KB Output is correct
7 Correct 31 ms 33140 KB Output is correct
8 Correct 360 ms 46980 KB Output is correct
9 Correct 323 ms 40440 KB Output is correct
10 Correct 843 ms 51240 KB Output is correct
11 Correct 403 ms 52344 KB Output is correct
12 Correct 416 ms 50796 KB Output is correct
13 Correct 28 ms 33144 KB Output is correct
14 Correct 380 ms 47080 KB Output is correct
15 Correct 89 ms 34552 KB Output is correct
16 Correct 1164 ms 51496 KB Output is correct
17 Correct 421 ms 50956 KB Output is correct
18 Correct 406 ms 50936 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33108 KB Output is correct
2 Correct 34 ms 33272 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 41 ms 33656 KB Output is correct
5 Correct 37 ms 33372 KB Output is correct
6 Correct 37 ms 33400 KB Output is correct
7 Correct 29 ms 33196 KB Output is correct
8 Correct 387 ms 46968 KB Output is correct
9 Correct 310 ms 40312 KB Output is correct
10 Correct 815 ms 51204 KB Output is correct
11 Correct 402 ms 52352 KB Output is correct
12 Correct 400 ms 50812 KB Output is correct
13 Correct 32 ms 33144 KB Output is correct
14 Correct 363 ms 46820 KB Output is correct
15 Correct 90 ms 34424 KB Output is correct
16 Correct 1135 ms 51576 KB Output is correct
17 Correct 404 ms 50872 KB Output is correct
18 Correct 406 ms 50908 KB Output is correct
19 Correct 895 ms 69624 KB Output is correct
20 Correct 880 ms 67240 KB Output is correct
21 Correct 896 ms 69752 KB Output is correct
22 Correct 876 ms 67064 KB Output is correct
23 Correct 914 ms 67232 KB Output is correct
24 Correct 925 ms 67192 KB Output is correct
25 Correct 963 ms 67192 KB Output is correct
26 Correct 906 ms 69628 KB Output is correct
27 Correct 895 ms 69564 KB Output is correct
28 Correct 900 ms 67020 KB Output is correct
29 Correct 899 ms 67368 KB Output is correct
30 Correct 887 ms 67236 KB Output is correct