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. struct Node
  25. {
  26.     int mx = -oo;
  27.     int place = -1;
  28. } NEUTRAL;
  29.  
  30. struct SegTree
  31. {
  32.     int size;
  33.     vector<Node> tree;
  34.  
  35.     SegTree(int n)
  36.     {
  37.         size = 1;
  38.         while (size < n)
  39.             size *= 2;
  40.         tree.resize(2 * size);
  41.     }
  42.  
  43.     Node merage(const Node &a, const Node &b)
  44.     {
  45.         Node res;
  46.         if (a.mx >= b.mx)
  47.         {
  48.             res.mx = a.mx;
  49.             res.place= a.place;
  50.         }
  51.         else
  52.         {
  53.             res.mx = b.mx;
  54.             res.place= b.place;
  55.         }
  56.         return res;
  57.     }
  58.     void build(vector<int> &a, int x, int lx, int rx)
  59.     {
  60.         if (rx - lx == 1)
  61.         {
  62.             if (lx < a.size())
  63.             {
  64.                 tree[x].mx = 0;
  65.                 tree[x].place = lx;
  66.             }
  67.             return;
  68.         }
  69.         int m = (lx + rx) / 2;
  70.         build(a, 2 * x + 1, lx, m);
  71.         build(a, 2 * x + 2, m, rx);
  72.         tree[x] = merage(tree[2 * x + 1], tree[2 * x + 2]);
  73.     }
  74.  
  75.     void update(int i, int v, int x, int lx, int rx)
  76.     {
  77.         if (rx - lx == 1)
  78.         {
  79.             tree[x].mx += v;
  80.             return;
  81.         }
  82.         int m = (lx + rx) / 2;
  83.         if (i < m)
  84.             update(i, v, 2 * x + 1, lx, m);
  85.         else
  86.             update(i, v, 2 * x + 2, m, rx);
  87.         tree[x] = merage(tree[2 * x + 1], tree[2 * x + 2]);
  88.     }
  89.  
  90.     // zero based Range Query [l,r)
  91.     Node query(int l, int r, int x, int lx, int rx)
  92.     {
  93.         if (lx >= r || rx <= l)
  94.             return NEUTRAL;
  95.         if (lx >= l && rx <= r)
  96.             return tree[x];
  97.         int m = (lx + rx) / 2;
  98.         return merage(query(l, r, 2 * x + 1, lx, m), query(l, r, 2 * x + 2, m, rx));
  99.     }
  100.  
  101.     void build(vector<int> &a) { build(a, 0, 0, size); }
  102.     void update(int i, int v) { update(i, v, 0, 0, size); }
  103.     Node query(int l, int r) { return query(l, r, 0, 0, size); }
  104. };
  105.  
  106. void Guardiola()
  107. {
  108.     int n, q;
  109.     cin >> n >> q;
  110.     vector<int> a(n + 2);
  111.     SegTree st(n + 2);
  112.     st.build(a);
  113.     int last = 1;
  114.     for (int i = 1; i <= q; i++)
  115.     {
  116.         int id, v;
  117.         cin >> id >> v;
  118.         int prev = st.query(1, n + 1).place;
  119.         st.update(id, v);
  120.         int cur = st.query(1, n + 1).place;
  121.         if (cur != prev)
  122.             last = i;
  123.     }
  124.     cout << last << endl;
  125. }
  126.  
  127. signed main()
  128. {
  129.     pep_Guardiola;
  130.     io();
  131.     int t = 1;
  132.     cin >> t;
  133.     while (t--)
  134.         Guardiola();
  135.     return 0;
  136. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/N27LnJ
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!