SHARE
TWEET

Untitled

a guest Nov 4th, 2017 248 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.    
  3. using namespace std;
  4.    
  5. const int dd = (int)4e5 + 1;
  6. const int inf = (1ll << 31) - 1;
  7.  
  8. vector<pair<int, int> > Q;
  9. vector<int> iP;
  10.  
  11. void up(int i) {
  12.     if (i == 1) return;
  13.     if (Q[i / 2] < Q[i]) {
  14.         swap(Q[i], Q[i / 2]);
  15.         swap(iP[Q[i].second], iP[Q[i / 2].second]);
  16.         up(i / 2);
  17.     }
  18. }
  19.  
  20. void down(int i) {
  21.     int f = 0;
  22.     if (i * 2 < (int)Q.size() && Q[i] < Q[i * 2]) {
  23.         swap(Q[i], Q[i * 2]);
  24.         swap(iP[Q[i].second], iP[Q[i * 2].second]);
  25.         f = 1;
  26.     }
  27.     if (i * 2 + 1 < (int)Q.size() && Q[i] < Q[i * 2 + 1]) {
  28.         if (f) {
  29.             swap(Q[i], Q[i * 2]);
  30.             swap(iP[Q[i].second], iP[Q[i * 2].second]);
  31.         }  
  32.         swap(Q[i], Q[i * 2 + 1]);
  33.         swap(iP[Q[i].second], iP[Q[i * 2 + 1].second]);
  34.         f = 2;
  35.     }
  36.     if (f) down(i * 2 + f - 1);
  37. }
  38.  
  39. int get() {
  40.     return Q[1].first;
  41. }
  42.  
  43. void eget() {
  44.     swap(Q[1], Q.back());
  45.     swap(iP[Q[1].second], iP[Q.back().second]);
  46.     iP[Q.back().second] = -1;
  47.     Q.pop_back();
  48.     if ((int)Q.size() > 1) down(1);
  49. }
  50.  
  51. void dk(int a, int b) {
  52.     Q[a].first = b;
  53.     up(a);
  54. }
  55.  
  56. void del(int a) {
  57.     dk(a, inf);
  58.     eget();
  59. }
  60.  
  61. void push(int x) {
  62.     Q.push_back({ x, (int)iP.size() });
  63.     iP.push_back((int)Q.size() - 1);
  64.     up((int)Q.size() - 1);
  65. }
  66.  
  67. vector<pair<int, int> > add[dd];
  68. vector<int> ded[dd];
  69.  
  70. int main() {
  71.     int n, m;
  72.     scanf("%d %d", &n, &m);
  73.     Q.push_back({ -1, 0 });
  74.     for (int i = 0; i < m; ++i) {
  75.         int l, r, x;
  76.         scanf("%d %d %d", &l, &r, &x);
  77.         --l, --r;
  78.         add[l].push_back({ x, r });
  79.     }
  80.  
  81.     int cnt = 0;
  82.     for (int i = 0; i < n; ++i) {
  83.         for (auto j : add[i]) {
  84.             push(j.first);
  85.             ded[j.second + 1].push_back(cnt++);
  86.         }
  87.         for (int j : ded[i])
  88.             del(iP[j]);
  89.         if ((int)Q.size() == 1) printf("1 ");
  90.         else printf("%d ", get());
  91.     }
  92.     return 0;
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top