Submission #162598

#	Time	Username	Problem	Language	Result	Execution time	Memory
162598		12tqian	Wall (IOI14_wall)	C++14	100 / 100	1164 ms	69752 KiB

wall

#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 (stderr)

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39