oj.uz

답안 #161534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161534 2019-11-03T02:53:34 Z 12tqian 벽 (IOI14_wall) C++14
0 / 100
 1000 ms 74484 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];
pi comb(pi a, pi b){
    if(a.f == -INF && b.f == -INF) {
        if(a.s<b.s) return a;
        return b;
    }
    if(a.s == INF && b.s == INF){
        if(a.f<b.f) return b;
        return a;
    }
    return b;
}
pi merge(pi a, pi b){
    return mp(min(a.f, b.f), max(a.s, b.s));
}
void pull(int ind){
    seg[ind] = merge(seg[2*ind], seg[2*ind+1]);
}
void build(){
    f0r(i, 2*SZ) lazy[i] = mp(-INF, INF);
    f0r(i, 2*SZ) seg[i] = mp(0, 0);
}
void push(int ind, int L, int R){
    seg[ind] = comb(seg[ind], lazy[ind]);
    if(L != R){
        lazy[2*ind] = comb(lazy[2*ind], lazy[ind]);
        lazy[2*ind+1] = comb(lazy[2*ind+1], lazy[ind]);
    }
    lazy[ind] = mp(-INF, INF);
}
void upd(int l, int r, pi val, int ind = 1, int L = 0, int R = SZ - 1){
    push(ind, L, R);
    if(r<L || R<l) return;
    if(l<= L && R<= r){
        lazy[ind] = val;
        push(ind, L, R);
        return;
    }
    int M = (L + R)/2;
    upd(l, r, val, 2*ind, L, M); upd(l, r, val, 2*ind+1, M+1, R);
    pull(ind);
}

pi query(int l, int r, int ind = 1, int L = 0, int R = SZ - 1){
    push(ind, L, R);
    if(l>R || L>r) return mp(-INF, INF);
    if(l<= L && R<= r) return seg[ind];
    int M = (L+R)/2;
    return comb(query(l, r, 2*ind, L, M), query(l, r, 2*ind+1, M+1, R));
}

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) {
        auto v = query(i, i);
        if(v.f == -INF) finalHeight[i] = v.s;
        else if(v.s == INF) finalHeight[i] = v.f;
        else{
            assert(v.f == v.s);
            finalHeight[i] = v.f;
        }
    }
}

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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 65912 KB Output is correct
2 Correct 63 ms 66168 KB Output is correct
3 Incorrect 59 ms 66040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 66028 KB Output is correct
2 Correct 598 ms 73856 KB Output is correct
3 Correct 456 ms 69368 KB Output is correct
4 Incorrect 1000 ms 74484 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 66040 KB Output is correct
2 Correct 63 ms 66040 KB Output is correct
3 Incorrect 60 ms 66040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 65912 KB Output is correct
2 Correct 70 ms 66028 KB Output is correct
3 Incorrect 57 ms 66052 KB Output isn't correct
4 Halted 0 ms 0 KB -