| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 161537 |
2019-11-03T02:55:54 Z |
12tqian |
Wall (IOI14_wall) |
C++14 |
|
1077 ms |
74520 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(-INF, 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);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
65916 KB |
Output is correct |
| 2 |
Correct |
58 ms |
66108 KB |
Output is correct |
| 3 |
Incorrect |
56 ms |
66040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
65912 KB |
Output is correct |
| 2 |
Correct |
598 ms |
73868 KB |
Output is correct |
| 3 |
Correct |
474 ms |
69352 KB |
Output is correct |
| 4 |
Incorrect |
1077 ms |
74520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
65912 KB |
Output is correct |
| 2 |
Correct |
58 ms |
66120 KB |
Output is correct |
| 3 |
Incorrect |
56 ms |
66040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
65912 KB |
Output is correct |
| 2 |
Correct |
63 ms |
66040 KB |
Output is correct |
| 3 |
Incorrect |
58 ms |
65968 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
