| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 702557 | wcwu | Wall (IOI14_wall) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include<random>
using namespace std;
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("O3")*/
/*#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")//for codeforces*/
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
typedef map<ll, ll> mll;
const int MOD1=1e9+7;
const int MOD2=998244353;
const int iINF=INT_MAX;
const ll INF=LLONG_MAX;
const ld PI=3.14159265358979323846;
ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}
ll fpow(ll a,ll b,ll m) {
if(!b) return 1;
ll ans=fpow(a*a%m,b/2,m);
return (b%2?ans*a%m:ans);
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define dbg(n) cerr<<#n<<": "<<n<<"\n";
#define optline cout<<"\n";
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define irep(i,m,n) for(ll i=m;i>=n;i--)
#define F first
#define S second
#define All(c) c.begin(), c.end()
#define pb push_back
#define eb emplace_back
//#define mp make_pair
#define uni(c) c.resize(distance(c.begin(), unique(c.begin(), c.end())))
#define unisort(c) sort(c.begin(), c.end());uni(c)
const int N=2e6+5;
ll n, k;
struct Node{
ll val, mn, mx;
Node *lc, *rc;
Node() {val=mx=0; mn=N; lc=rc=NULL;}
void pull() {
//?
}
};
Node* build(int L, int R) {
Node *node=new Node();
if(L==R) {
return node;
}
int mid=(L+R)>>1;
node->lc=build(L, mid);
node->rc=build(mid+1, R);
node->pull();
return node;
}
void oper(Node *node, ll up, ll down) {
node->mn=min(node->mn, down);
node->mn=max(node->mn, up);
node->mx=max(node->mx, up);
node->mx=min(node->mx, down);
}
void modifymn(Node *node, int L, int R, int ql, int qr, ll d) {
if(ql>R || qr<L) return;
if(ql<=L && R<=qr) {
node->mn=min(node->mn, d);
node->mx=min(node->mx, d);
return;
}
int mid=(L+R)>>1;
oper(node->lc, node->mx, node->mn);
oper(node->rc, node->mx, node->mn);
node->mx=0;
node->mn=N;
modifymn(node->lc, L, mid, ql, qr, d);
modifymn(node->rc, mid+1, R, ql, qr, d);
}
void modifymx(Node *node, int L, int R, int ql, int qr, ll d) {
if(ql>R || qr<L) return;
if(ql<=L && R<=qr) {
node->mn=max(node->mn, d);
node->mx=max(node->mx, d);
return;
}
int mid=(L+R)>>1;
oper(node->lc, node->mx, node->mn);
oper(node->rc, node->mx, node->mn);
node->mx=0;
node->mn=N;
modifymx(node->lc, L, mid, ql, qr, d);
modifymx(node->rc, mid+1, R, ql, qr, d);
}
void query(Node *node, int L, int R) {
if(L==R) {
cout<<min(node->mn, node->mx)<<"\n";
return;
}
int mid=(L+R)>>1;
oper(node->lc, node->mx, node->mn);
oper(node->rc, node->mx, node->mn);
node->mx=0;
node->mn=N;
query(node->lc, L, mid);
query(node->rc, mid+1, R);
}
signed main() {
IOS
cin>>n>>k;
Node *node=build(0, n-1);
while(k--) {
ll ty, l, r, d;
cin>>ty>>l>>r>>d;
if(ty==1) modifymx(node, 0, n-1, l, r, d);
else modifymn(node, 0, n-1, l, r, d);
}
query(node, 0, n-1);
}