fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "raspored"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 6e5 + 5;
  38. int numPerson, numQuery, sizeTree;
  39. ii person[N];
  40. vector<int> compress;
  41. int curUsed[N];
  42.  
  43. struct Query {
  44.     int pos, limit, doing;
  45. } Q[N];
  46.  
  47. struct Node {
  48.     ll sumLimit, sumDoing, doingMul, lazy;
  49.     int cnt;
  50.  
  51.     Node(ll _sumLimit = 0, ll _sumDoing = 0, ll _doingMul = 0, ll _lazy = 0, int _cnt = 0):
  52.         sumLimit(_sumLimit), sumDoing(_sumDoing), doingMul(_doingMul), lazy(_lazy), cnt(_cnt) {}
  53.  
  54.     friend Node combine(const Node &L, const Node &R) {
  55.         Node res;
  56.         res.sumLimit = L.sumLimit + R.sumLimit;
  57.         res.sumDoing = L.sumDoing + R.sumDoing;
  58.         res.doingMul = L.doingMul + R.doingMul;
  59.         res.cnt = L.cnt + R.cnt;
  60.         return res;
  61.     }
  62. } node[N << 2];
  63.  
  64. void pushDown(int id) {
  65.     if (node[id].lazy) {
  66.         node[id << 1].doingMul += node[id << 1].sumDoing * node[id].lazy;
  67.         node[id << 1].lazy += node[id].lazy;
  68.  
  69.         node[id << 1 | 1].doingMul += node[id << 1 | 1].sumDoing * node[id].lazy;
  70.         node[id << 1 | 1].lazy += node[id].lazy;
  71.  
  72.         node[id].lazy = 0;
  73.     }
  74. }
  75.  
  76. void updatePos(int pos, int limit, int doing, int realPos, int sign) {
  77.     int id = 1, l = 1, r = sizeTree;
  78.     while(l < r) {
  79.         pushDown(id);
  80.         int mid = (l + r) >> 1;
  81.         if (pos > mid) id = (id << 1 | 1), l = mid + 1;
  82.         else id = (id << 1), r = mid;
  83.     }
  84.  
  85.     node[id].doingMul += 1ll * doing * (realPos - 1) * sign;
  86.     node[id].sumDoing += doing * sign;
  87.     node[id].sumLimit += limit * sign;
  88.     node[id].cnt += sign;
  89.  
  90.     while(id) {
  91.         id >>= 1;
  92.         node[id] = combine(node[id << 1], node[id << 1 | 1]);
  93.     }
  94. }
  95.  
  96. void updateDoing(int id, int l, int r, int u, int v, int sign) {
  97.     if (l > v || r < u || u > v) return;
  98.     if (u <= l && r <= v) {
  99.         node[id].doingMul += node[id].sumDoing * sign;
  100.         node[id].lazy += sign;
  101.         return;
  102.     }
  103.     pushDown(id);
  104.     int mid = (l + r) >> 1;
  105.     updateDoing(id << 1, l, mid, u, v, sign);
  106.     updateDoing(id << 1 | 1, mid + 1, r, u, v, sign);
  107.     node[id] = combine(node[id << 1], node[id << 1 | 1]);
  108. }
  109.  
  110. int getCnt(int id, int l, int r, int u, int v) {
  111.     if (l > v || r < u || u > v) return 0;
  112.     if (u <= l && r <= v) return node[id].cnt;
  113.     pushDown(id);
  114.     int mid = (l + r) >> 1;
  115.     int L = getCnt(id << 1, l, mid, u, v);
  116.     int R = getCnt(id << 1 | 1, mid + 1, r, u, v);
  117.     return L + R;
  118. }
  119.  
  120. int findPos(int k) {
  121.     int id = 1, l = 1, r = sizeTree;
  122.     while(l < r) {
  123.         pushDown(id);
  124.         int mid = (l + r) >> 1;
  125.         if (node[id << 1].cnt >= k) {
  126.             id = (id << 1);
  127.             r = mid;
  128.         } else {
  129.             k -= node[id << 1].cnt;
  130.             id = (id << 1 | 1);
  131.             l = mid + 1;
  132.         }
  133.     }
  134.     return l;
  135. }
  136.  
  137. ll solve() {
  138.     // sum(t[i]) - sum(d[i] * (n - i + 1)) = sum(t[i]) - sum(d[i] * n) + sum(d[i] * (i - 1))
  139.     // cout << node[1].sumLimit << ' ' << node[1].sumDoing << ' ' << node[1].doingMul << '\n';
  140.     return node[1].sumLimit - node[1].sumDoing * numPerson + node[1].doingMul;
  141. }
  142.  
  143. int getCompress(int x) {
  144.     int pos = lower_bound(all(compress), x) - compress.begin() + 1;
  145.     return pos + (curUsed[pos]++);
  146. }
  147.  
  148. int getRealPos(int pos) {
  149.     int res = getCnt(1, 1, sizeTree, 1, pos - 1);
  150.     return res + 1;
  151. }
  152.  
  153. int traceRealPos(int realPos) {
  154.     if (realPos > node[1].cnt) return sizeTree + 1;
  155.     int res = findPos(realPos);
  156.     return res;
  157. }
  158.  
  159. void init(void) {
  160.     int subtask; cin >> subtask;
  161.     cin >> numPerson >> numQuery;
  162.     FOR(i, 1, numPerson) cin >> person[i].fi >> person[i].se, compress.pb(person[i].se);
  163.     FOR(i, 1, numQuery) cin >> Q[i].pos >> Q[i].limit >> Q[i].doing, compress.pb(Q[i].doing);
  164.     sizeTree = numPerson + numQuery;
  165. }
  166.  
  167. void process(void) {
  168.     sort(all(compress));
  169.     FOR(i, 1, numPerson) person[i].se = getCompress(person[i].se);
  170.     FOR(i, 1, numQuery) Q[i].doing = getCompress(Q[i].doing);
  171.  
  172.     FOR(i, 1, numPerson) {
  173.         int realPos = getRealPos(person[i].se);
  174.         updateDoing(1, 1, sizeTree, traceRealPos(realPos), sizeTree, +1);
  175.         updatePos(person[i].se, person[i].fi, compress[person[i].se - 1], realPos, +1);
  176.     }
  177.  
  178.     cout << solve() << ' ';
  179.  
  180.     FOR(j, 1, numQuery) {
  181.         int i = Q[j].pos;
  182.         int realPos = getRealPos(person[i].se);
  183.  
  184.         // erase old info
  185.         updatePos(person[i].se, person[i].fi, compress[person[i].se - 1], realPos, -1);
  186.         updateDoing(1, 1, sizeTree, traceRealPos(realPos), sizeTree, -1);
  187.  
  188.         // change new info
  189.         person[i].se = Q[j].doing;
  190.         person[i].fi = Q[j].limit;
  191.  
  192.         realPos = getRealPos(person[i].se);
  193.  
  194.         updateDoing(1, 1, sizeTree, traceRealPos(realPos), sizeTree, +1);
  195.         updatePos(person[i].se, person[i].fi, compress[person[i].se - 1], realPos, +1);
  196.  
  197.         cout << solve() << ' ';
  198.     }
  199. }
  200.  
  201. int main() {
  202.     ios_base::sync_with_stdio(0);
  203.     cin.tie(0); cout.tie(0);
  204.     if (fopen(task".inp", "r")) {
  205.         freopen(task".inp", "r", stdin);
  206.         freopen(task".out", "w", stdout);
  207.     }
  208.     int tc = 1;
  209. //    cin >> tc;
  210.     while(tc--) {
  211.         init();
  212.         process();
  213.     }
  214.     return 0;
  215. }
  216.  
Success #stdin #stdout 0.02s 101272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QFQD9e
language:
C++14 (gcc 8.3)
created:
2 days 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!