fork download
copy 
  1. #include <bits/stdc++.h>
  2. #ifndef ONLINE_JUDGE
  3. #include "debug.h"
  4. #else
  5. #define debug(...)
  6. #endif
  7. #define int long long
  8. #define oo LLONG_MAX >> 2
  9. #define all(x) x.begin(), x.end()
  10. #define allr(x) x.rbegin(), x.rend()
  11. #define pep_Guardiola        \
  12.     ios::sync_with_stdio(0); \
  13.     cin.tie(0);              \
  14.     cout.tie(0);
  15. using namespace std;
  16. void io()
  17. {
  18. #ifndef ONLINE_JUDGE
  19.     freopen("input.txt", "r", stdin);
  20.     // freopen("output.txt", "w", stdout);
  21. #endif
  22. }
  23.  
  24.  
  25. struct Node {
  26.     int mx = -oo;
  27.     int place = -1;
  28. } NEUTRAL;
  29.  
  30. struct SegTree {
  31.   int size;
  32.   vector<Node> tree;
  33.  
  34.   SegTree(int n) {
  35.     size = 1;
  36.     while (size < n)
  37.       size *= 2;
  38.     tree.resize(2 * size);
  39.   }
  40.  
  41.   Node merage(const Node &a, const Node &b) {
  42.     Node res;
  43.     if(a.mx >= b.mx){
  44.         res = a;
  45.     }else{
  46.         res = b;
  47.     }
  48.     return res;
  49.   }
  50.   void build(vector<int> &a, int x, int lx, int rx) {
  51.     if (rx - lx == 1) {
  52.       if (lx < a.size()) {
  53.        tree[x].place = lx; 
  54.       }
  55.       return;
  56.     }
  57.     int m = (lx + rx) / 2;
  58.     build(a, 2 * x + 1, lx, m);
  59.     build(a, 2 * x + 2, m, rx);
  60.     tree[x] = merage(tree[2 * x + 1], tree[2 * x + 2]);
  61.   }
  62.  
  63.  
  64.  
  65.   void update(int i, int v, int x, int lx, int rx) {
  66.     if (rx - lx == 1) {
  67.         tree[x].mx += v;
  68.       return;
  69.     }
  70.     int m = (lx + rx) / 2;
  71.     if (i < m)
  72.       update(i, v, 2 * x + 1, lx, m);
  73.     else
  74.       update(i, v, 2 * x + 2, m, rx);
  75.     tree[x] = merage(tree[2 * x + 1], tree[2 * x + 2]);
  76.   }
  77.  
  78.   // zero based Range Query [l,r)
  79.   Node query(int l, int r, int x, int lx, int rx)
  80.   {
  81.       if (lx >= r || rx <= l) return NEUTRAL;
  82.       if (lx >= l && rx <= r) return tree[x];
  83.       int m = (lx + rx)/2;
  84.       return merage(query(l, r, 2*x+1, lx, m),query(l, r, 2*x+2, m, rx));
  85.   }
  86.  
  87.  
  88.  
  89.   void build(vector<int> &a) { build(a, 0, 0, size); }
  90.   void update(int i, int v) { update(i, v, 0, 0, size);}
  91.   Node query(int l, int r) { return query(l, r, 0, 0, size); }
  92. };
  93.  
  94. void Guardiola()
  95. {
  96.     int n,q;
  97.     cin >> n >> q;
  98.     vector<int> a(n+2);
  99.     SegTree st(n+2);
  100.     st.build(a);
  101.     int last = 1;
  102.     for(int i = 1 ;i <= q;i++){
  103.         int id , v;
  104.         cin >> id >> v;
  105.         int prev = st.query(1,n+1).place;
  106.         st.update(id , v);
  107.         int cur = st.query(1,n+1).place;
  108.         if(cur != prev) last = i;
  109.     }
  110.     cout << last << endl;
  111. }
  112.  
  113. signed main()
  114. {
  115.     pep_Guardiola;
  116.     io();
  117.     int t = 1;
  118.     cin >> t;
  119.     while (t--)
  120.         Guardiola();
  121.     return 0;
  122. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/FSDxlQ
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!