Last active
May 31, 2021 09:51
-
-
Save dchular/bc22b21f7cc49e268d45b17057f06475 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#include <atcoder/lazysegtree> | |
#include <atcoder/segtree> | |
#define overload4(_1, _2, _3, _4, name, ...) name | |
#define rep1(n) for(ll i = 0; i < (n); ++i) | |
#define rep2(i, n) for(ll i = 0; i < (n); ++i) | |
#define rep3(i, a, b) for(ll i = (a); i < (b); ++i) | |
#define rep4(i, a, b, c) for(ll i = (a); i < (b); i += (c)) | |
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) | |
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i) | |
#define rrep(i,a,n) for (int i=n-1;i>=a;i--) | |
#define ALL(x) x.begin(),x.end() | |
#define pb push_back | |
#define mp make_pair | |
#define fi first | |
#define se second | |
#define pause "read -p 'Press Enter to continue...' var" | |
using namespace std; | |
using namespace atcoder; | |
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } | |
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } | |
/* | |
テスト通りますように | |
● | |
/⌒ヽ | |
| |/⌒ヽ(ヽ | |
(` ∥ー⌒) | | |
| ̄|| ̄ ̄ ̄ ̄ ̄| | |
|―||―――――| | |
| U | | |
| ̄ ̄ ̄ ̄ ̄ ̄ ̄| | |
|_______| | |
|―――――| | |
|―――――| | |
wwWwwWwWWw | |
*/ | |
typedef long long ll; | |
typedef vector<ll> vll; | |
typedef pair<ll,ll> pll; | |
//const ll INF = numeric_limits<ll>::max()/4; | |
const ll MAX = 200005; | |
const int MOD = 3; | |
int dx[4]={1,0,-1,0}; | |
int dy[4]={0,1,0,-1}; | |
using S = long long; | |
using F = long long; | |
const S INF = 8e18; | |
const F ID = 8e18; | |
S op(S a, S b){ return std::max(a, b); } | |
S e(){ return -INF; } | |
S mapping(F f, S x){ return (f == ID ? x : f); } | |
F composition(F f, F g){ return (f == ID ? g : f); } | |
F id(){ return ID; } | |
int main(){ | |
ll w, n; | |
cin >> w >> n; | |
vector<S> v; | |
rep(i,w) v.pb(0); | |
lazy_segtree<S, op, e, F, mapping, composition, id> seg(v); | |
rep(n){ | |
ll l, r; | |
cin >> l >> r; | |
ll height = seg.prod(l - 1, r) + 1; | |
seg.apply(l-1,r,height); | |
cout << height << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment