Submission #1182466

#TimeUsernameProblemLanguageResultExecution timeMemory
1182466swishy123Wall (IOI14_wall)C++20
0 / 100
14 ms22344 KiB
#include <iostream> #include <algorithm> #include <vector> #include <random> #include <chrono> #include <set> #include <map> #include <stack> #include <functional> #include <iomanip> #include <queue> #include <cassert> #include <complex> #include <cstring> #include <memory> #include <bitset> #include <sstream> #include <cmath> #include <numeric> #include <numbers> #include <fstream> #include "wall.h" using namespace std; #ifndef template #ifndef define #define ll long long #define ld long double #define pl pair<ll, ll> #define pi pair<int, int> #define nl cout << '\n'; #define x first #define y second #define cbit(x) __builtin_popcountll(x) #define uid(a, b) uniform_int_distribution<ll>(a, b)(rng) #define siz(x) (int)x.size() #endif #ifndef print void print(size_t x) {cout << x << ' ';} void print(int x) {cout << x << ' ';} void print(long long x) {cout << x << ' ';} void print(float x) {cout << x << ' ';} void print(long double x) {cout << x << ' ';} void print(char x) {cout << x << ' ';} void print(const char* x) {cout << x << ' ';} void print(bool x) {cout << x << ' ';} void print(string &x) {cout << x << ' ';} template<typename T, typename V> void print(pair<T, V> &p) {print(p.x); print(p.y);} template<typename T> void print(vector<T> v) {for (int i = 0; i < v.size(); i++) print(v[i]);} template<typename T> void print(vector<vector<T>> v) { for (int i = 0; i < v.size(); i++){ for (int j = 0; j < v[i].size(); j++) print(v[i][j]); nl; } } template <typename T, typename... V> void print(T t, V&&... v) {print(t); print(v...);} #endif #ifndef read void read(int &x) {cin >> x;} void read(long long &x) {cin >> x;} void read(unsigned &x) {cin >> x;} void read(unsigned long long &x) {cin >> x;} void read(float &x) {cin >> x;} void read(long double &x) {cin >> x;} void read(char &x) {cin >> x;} void read(string &x) {cin >> x;} void read(bool &x) {cin >> x;} template<typename T> void read(vector<T> &v) { for (int i = 0; i < v.size(); i++) read(v[i]); } template <typename T, typename... V> void read(T &t, V&... v) {read(t); read(v...);} #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> bool maxi(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template<class T> bool mini(T& a, const T& b) { return a > b ? a = b, 1 : 0; } template<class... Args> auto vec(size_t n, Args&&... args) { if constexpr(sizeof...(args) == 1) return vector(n, args...); else return vector(n, vec(args...)); } #endif using namespace std; const ll inf = 1e15; const ll def = 2e5+1; const ll mod = 998244353; template <typename T> class SegmentTree{ public: int n; T defv; vector<T> st; SegmentTree(){} SegmentTree(int n, T defv) : n(n), defv(defv){ st = vector<T>(4 * n, defv); } void update(int i, T v){ _update(0, n - 1, 0, i, v); } T get(int l, int r){ return _get(0, n - 1, l, r, 0); } private: T cmb(T l, T r){ return max(l, r); } void _update(int l, int r, int crr, int i, T v){ if (r < i || l > i) return; if (l == r){ st[crr] = v; return; } int mid = (l + r) / 2; _update(l, mid, crr * 2 + 1, i, v); _update(mid + 1, r, crr * 2 + 2, i, v); st[crr] = cmb(st[crr * 2 + 1], st[crr * 2 + 2]); } T _get(int l, int r, int ql, int qr, int crr){ if (qr < l || ql > r) return defv; if (l >= ql && r <= qr) return st[crr]; int mid = (l + r) / 2; return cmb(_get(l, mid, ql, qr, crr * 2 + 1), _get(mid + 1, r, ql, qr, crr * 2 + 2)); } }; SegmentTree<int> st1(100001, -1e9), st2(100001, -1e9); int walk1(int l, int r, int crr, int vall, int valr){ if (l == r) return l; int mid = (l + r) / 2; int lval = max(st2.st[crr * 2 + 1], vall), rval = max(st1.st[crr * 2 + 2], valr); //print(l, r, lval, rval); nl; if (rval > lval) return walk1(mid + 1, r, crr * 2 + 2, lval, valr); else return walk1(l, mid, crr * 2 + 1, vall, rval); } int walk2(int l, int r, int crr, int vall, int valr){ if (l == r) return l; int mid = (l + r) / 2; int lval = max(st2.st[crr * 2 + 1], vall), rval = max(st1.st[crr * 2 + 2], valr); if (lval > rval) return walk2(l, mid, crr * 2 + 1, vall, rval); else return walk2(mid + 1, r, crr * 2 + 2, lval, valr); } vector<set<int>> bruh1(100001), bruh2(100001); void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ vector<vector<tuple<int, int, int>>> event(n + 1); for (int i = 0; i < k; i++){ event[left[i]].push_back({op[i], i, height[i] + 1}); event[right[i] + 1].push_back({op[i], i, -(height[i] + 1)}); } for (int i = 0; i <= 100000; i++){ bruh1[i].insert(-1e9); bruh2[i].insert(-1e9); } st1.update(0, -1); for (int i = 0; i < n; i++){ for (auto [type, pos, x] : event[i]){ int y = abs(x) - 1; if (x < 0){ if (type == 1) bruh1[-x - 1].erase(pos); else bruh2[-x - 1].erase(pos); } else{ if (type == 1) bruh1[x - 1].insert(pos); else bruh2[x - 1].insert(pos); } if (type == 1) st1.update(y, *bruh1[y].rbegin()); else st2.update(y, *bruh2[y].rbegin()); } print(i); nl; for (int j = 0; j < n; j++) print(st1.get(j, j)); nl; for (int j = 0; j < n; j++) print(st2.get(j, j)); nl; int pos1 = walk1(0, 100000, 0, -1e9, -1e9); int pos2 = walk2(0, 100000, 0, -1e9, -1e9); int _pos = min(pos1, pos2); finalHeight[i] = _pos; } } // void solve(){ // int n, k; // read(n, k); // int op[k], left[k], right[k], height[k]; // for (int i = 0; i < k; i++) // read(op[i], left[i], right[i], height[i]); // int finalHeight[n]; // buildWall(n, k, op, left, right, height, finalHeight); // for (int i = 0; i < n; i++) // print(finalHeight[i]); // } // /* // */ // int32_t main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // if (ifstream("input.txt").good()){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // } // int t; // t = 1; // while (t--){ // solve(); // nl; // } // } /* for x to be answer max pos + > max pos - less than x or max pos - > max pos + more than x */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...