Maratona/e.cpp at master · bcs5/Maratona · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;

#define all(foo) foo.begin(), foo.end()

#define sc(a) scanf("%d", &a)
#define sc2(a,b) scanf("%d%d", &a, &b)
#define sc3(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define pri(x) printf("%d\n", x)

#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define x first
#define y second
typedef pair<int, int> ii;
const int mx = 1123456;
int n, t[2 * mx];

void update(int v, int l, int r) {
  for(l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
    if(l&1) t[l++] += v; // Merge
    if(r&1) t[--r] += v; // Merge
  }
}

int query(int p) {
  int res = 0;
  for(p += n; p > 0; p >>= 1) res += t[p]; // Merge
  return res;
}

void push() { // push modifications to leafs
  for(int i = 1; i < n; i++) {
    t[i<<1] += t[i]; // Merge
    t[i<<1|1] += t[i]; // Merge
    t[i] = 0;
  }
}

template <class T, class C = std::less<T>>
struct MaxQueue {
  MaxQueue() {
    clear();
  }

  void clear() {
    id = 0;
    q.clear();
  }

  void push(T x) {
    std::pair<int, T> nxt(1, x);
    while(q.size() > id && cmp(q.back().second, x)) {
      nxt.first += q.back().first;
      q.pop_back();
    }
    q.push_back(nxt);
  }

  T qry() {
    return q[id].second;
  }

  void pop() {
    q[id].first--;
    if(q[id].first == 0) {
      id++;
    }
  }
private:
  std::vector<std::pair<int, T>> q;
  int id;
  C cmp;
};
int v[mx];
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int m, w;
  cin >> m >> w;
  n = w;
  for (int i = 0; i < m; i++) {
    int k;
    cin >> k;
    vector<ii> ev;
    set<int> cx;
    for (int j = 1; j <= k; j++) {
      cin >> v[j];
      ev.push_back({j-1, -j});
      ev.push_back({w-(k-(j-1)), j});
      //cout << j << " " << (w-(k-j)) << endl;
      cx.insert(j-1);
      cx.insert((w-(k-(j-1))));
    }
    /*if (w != k) {
      ev.push_back({0, w+1});
      ev.push_back({w-k-1, w+1});

      ev.push_back({w-1-(w-k), w+1});
      ev.push_back({w-1, w+1});
      cx.insert(w-k-1);
      cx.insert(w-1-(w-k));
      cx.insert(w-1);
    }*/
    sort(all(ev));
    multiset<int> s;
    int t = 0, last = -1;
    for (auto u : cx) {
      while (t < ev.size() && ev[t] <= ii{u, 0}) {
        s.insert(v[-ev[t++].y]);
      }
      cout << last+1 << " " << u << " " << *s.rbegin() << endl;
      update(last+1, u, *s.rbegin());
      while (t < ev.size() && ev[t] <= ii{u, 1e9}) {
        s.erase(s.find(v[ev[t].y]));
        cout << "rem " << v[ev[t].y] << endl;
        t++;
      }
      last = u;
    }
    cout << endl;
  }
  push();
  for (int i = 0; i < w; i++) {
    cout << query(i) << " \n"[i == w-1];
  }
}