Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: C. First element at least X
- // Contest: Codeforces - ITMO Academy: pilot course - Segment Tree, part 1 - Step 2
- // URL: https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/C
- // Memory Limit: 1024 MB
- // Time Limit: 1000 ms
- // Parsed on: 14-10-2021 15:10:54 IST (UTC+05:30)
- // Author: Kapil Choudhary
- // ********************************************************************
- // कर्मण्येवाधिकारस्ते मा फलेषु कदाचन |
- // मा कर्मफलहेतुर्भूर्मा ते सङ्गोऽस्त्वकर्मणि || १.४७ ||
- // ********************************************************************
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ld long double
- #define ull unsigned long long
- #define pb push_back
- #define ppb pop_back
- #define pf push_front
- #define ppf pop_front
- #define mp make_pair
- #define F first
- #define S second
- #define PI 3.1415926535897932384626
- #define sz(x) ((int)(x).size())
- #define vset(v, n, val) v.clear(); v.resize(n, val)
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<ll> vll;
- typedef vector<ull> vull;
- typedef vector<bool> vb;
- typedef vector<char> vc;
- typedef vector<string> vs;
- typedef vector<pii> vpii;
- typedef vector<pll> vpll;
- typedef vector<vi> vvi;
- typedef vector<vll> vvll;
- typedef vector<vull> vvull;
- typedef vector<vb> vvb;
- typedef vector<vc> vvc;
- typedef vector<vs> vvs;
- /************************************************** DEBUGGER *******************************************************************************************************/
- #ifndef ONLINE_JUDGE
- #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
- #else
- #define debug(x)
- #endif
- void _print(ll t) { cerr << t; }
- void _print(int t) { cerr << t; }
- void _print(string t) { cerr << t; }
- void _print(char t) { cerr << t; }
- void _print(ld t) { cerr << t; }
- void _print(double t) { cerr << t; }
- void _print(ull t) { cerr << t; }
- template <class T, class V> void _print(pair <T, V> p);
- template <class T> void _print(vector <T> v);
- template <class T> void _print(vector <vector<T>> v);
- template <class T> void _print(set <T> v);
- template <class T, class V> void _print(map <T, V> v);
- template <class T> void _print(multiset <T> v);
- template <class T, class V> void _print(multimap <T, V> v);
- template <class T> void _print(queue <T> v);
- template <class T> void _print(priority_queue <T> v);
- template <class T> void _print(stack <T> s);
- // modify it's definition below as per need such as it can be used for STL containers with custom args passed
- template <class T> void _print(T v);
- template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
- template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
- template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
- template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
- template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
- template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
- template <class T, class V> void _print(multimap <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
- template <class T> void _print(queue <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.front()); v.pop(); cerr << " "; } cerr << "]"; }
- template <class T> void _print(priority_queue <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.top()); v.pop(); cerr << " "; } cerr << "]"; }
- template <class T> void _print(stack <T> v) { cerr << "[ "; while(!v.empty()) {_print(v.top()); v.pop(); cerr << " "; } cerr << "]"; }
- template <class T> void _print(T v) { }
- /*******************************************************************************************************************************************************************/
- mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
- int rng(int lim) {
- uniform_int_distribution<int> uid(0,lim-1);
- return uid(rang);
- }
- const int INF = 0x3f3f3f3f;
- const int mod = 1e9+7;
- ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
- while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
- ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
- ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
- /******************************************************************************************************************************/
- /*
- KEYNOTES:
- ------------------------------------------------------------------------------------------
- merge(X,identity_element) = X
- ------------------------------------------------------------------------------------------
- // (i.e no transformation at all or if we combine any new update with the identity update
- // it should give the newer update)
- identity_transformation.combine(X) = X
- ------------------------------------------------------------------------------------------
- ALWAYS: older_update.combine(newer_update)
- ------------------------------------------------------------------------------------------
- */
- // this structure depends on the nature of query
- struct node {
- // 1. change(s) required
- // use more variables if you want more information
- // these default values should be identity_element
- int mx = -INF;
- node() {}
- node(int val) {
- // 2. change(s) required
- mx = val;
- }
- // associative merging function, store the thing you wanna query
- void merge(const node &l, const node &r){
- // 3. change(s) required
- mx = max(l.mx, r.mx);
- }
- };
- // this structure depends on the nature of update
- struct update {
- // 4. change(s) required
- // use more variables if you want more information
- // these default values should be identity_transformation or identity_update
- int y = 0;
- update() {}
- update(int val) {
- // 5. change(s) required
- y = val;
- }
- // combine the current update with the other update (see keynotes)
- // basically combine older lazy value(s) (if exist) with newer one(s).
- // for this function, you can be sure that the "other" is newer than current
- void combine(update &other, const int32_t &tl, const int32_t &tr) {
- // 6. change(s) required
- y = other.y;
- }
- // store the correct information in the node x
- void apply(node &x, const int32_t &tl, const int32_t &tr) {
- // 7. change(s) required
- x.mx = y;
- }
- };
- template<typename node, typename update>
- struct segtree {
- int len;
- vector<node> t;
- vector<update> u;
- vector<bool> lazy;
- node identity_element;
- update identity_transformation;
- segtree(int l) {
- len = l;
- t.clear(); t.resize(4 * len);
- u.clear(); u.resize(4 * len);
- lazy.clear(); lazy.resize(4 * len);
- identity_element = node();
- identity_transformation = update();
- }
- void pushdown(const int32_t &v, const int32_t &tl, const int32_t &tr) {
- if(!lazy[v]) return;
- int32_t tm = (tl + tr) >> 1;
- apply(v << 1, tl, tm, u[v]);
- apply((v << 1) | 1, tm + 1, tr, u[v]);
- u[v] = identity_transformation;
- lazy[v] = 0;
- }
- void apply(const int32_t &v, const int32_t &tl, const int32_t &tr, update upd) {
- if(tl != tr) {
- lazy[v] = 1;
- u[v].combine(upd, tl, tr);
- }
- upd.apply(t[v], tl, tr);
- }
- template<typename T>
- void build(const T &arr, const int32_t &v, const int32_t &tl, const int32_t &tr) {
- if(tl == tr) {
- t[v] = arr[tl];
- return;
- }
- int32_t tm = (tl + tr) >> 1;
- build(arr, v << 1, tl, tm);
- build(arr, (v << 1) | 1, tm + 1, tr);
- t[v].merge(t[v << 1],t[(v << 1) | 1]);
- }
- node query(const int32_t &v, const int32_t &tl, const int32_t &tr, const int32_t &l, const int32_t &r) {
- if(l > tr || r < tl) {
- return identity_element;
- }
- if(tl >= l && tr <= r){
- return t[v];
- }
- pushdown(v, tl, tr);
- int32_t tm = (tl + tr) >> 1;
- node a = query(v << 1, tl, tm, l, r), b = query((v << 1) | 1, tm + 1, tr, l, r), ans;
- ans.merge(a, b);
- return ans;
- }
- void rupd(const int32_t &v, const int32_t &tl, const int32_t &tr, const int32_t &l, const int32_t &r, const update &upd) {
- if(l > tr || r < tl){
- return;
- }
- if(tl >= l && tr <= r){
- apply(v,tl,tr,upd);
- return;
- }
- pushdown(v, tl, tr);
- int32_t tm = (tl + tr) >> 1;
- rupd(v << 1, tl, tm, l, r, upd);
- rupd((v << 1) | 1, tm + 1, tr, l, r, upd);
- t[v].merge(t[v << 1], t[(v << 1) | 1]);
- }
- public:
- template<typename T>
- void build(const T &arr) {
- build(arr, 1, 0, len - 1);
- }
- node query(const int32_t &l,const int32_t &r) {
- return query(1, 0, len - 1, l, r);
- }
- void rupd(const int32_t &l, const int32_t &r, const update &upd) {
- rupd(1, 0, len - 1, l, r, upd);
- }
- };
- // https://www.youtube.com/watch?v=Hooe5ORdFsc
- void solve()
- {
- int n, m; cin >> n >> m;
- vi v(n);
- for(int i = 0; i < n; i++) cin >> v[i];
- struct segtree<node, update> s(n);
- s.build(v);
- while(m--) {
- int tp; cin >> tp;
- if(tp == 1) {
- int idx, val; cin >> idx >> val;
- s.rupd(idx, idx, val);
- }
- else {
- int x; cin >> x;
- int L = 0, R = n - 1;
- int ans = INF;
- while(L <= R) {
- int mid = L + ((R - L) >> 1);
- if(s.query(L, mid).mx < x) L = mid + 1;
- else ans = min(ans, mid), R = mid - 1;
- }
- if(ans == INF) ans = -1;
- cout << ans << "\n";
- }
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- srand(chrono::high_resolution_clock::now().time_since_epoch().count());
- // #ifndef ONLINE_JUDGE
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- // #endif
- // #ifndef ONLINE_JUDGE
- // freopen("error.txt", "w", stderr);
- // #endif
- int t = 1;
- // int test = 1;
- // cin >> t;
- while(t--) {
- // cout << "Case #" << test++ << ": ";
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement