fork download
copy 
  1. #pragma comment(linker, "/STACK:64000000")
  2. #include <algorithm>
  3. #include <memory.h>
  4. #include <cstdio>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <string>
  8. #include <cassert>
  9. #include <map>
  10. #include <set>
  11. #include <vector>
  12. #include <queue>
  13.  
  14. using namespace std;
  15. #define prev privet1
  16. #define next privet2
  17. #define y1 privet3
  18. #define rank privet4
  19. #define left privet5
  20. #define right privet6
  21. #define y0 privet7
  22.  
  23. const double pi = 3.141592653589793238;
  24.  
  25. void ensureLimit(long long n, long long l, long long r)
  26. {
  27.     assert(l <= n && n <= r);
  28. }
  29.  
  30. struct Segment {
  31.     int l, r, x;
  32. };
  33.  
  34.  
  35. const int MAX_M = 300333;
  36. const int MAX_N = MAX_M;
  37.  
  38. int o[MAX_M];
  39. int intend[MAX_N];
  40. int ans[MAX_N];
  41. long long add[MAX_M];
  42. bool known[MAX_M];
  43. long long a[MAX_M];
  44. long long sum[MAX_N];
  45. long long oldSum[MAX_N];
  46. vector<int> list[MAX_N];
  47.  
  48. Segment s[3333];
  49.  
  50.  
  51. int main() {
  52.     int n, m;
  53.     scanf("%d%d", &n, &m);
  54.     for (int i = 1; i <= m; i++) {
  55.         scanf("%d", &o[i]);
  56.         list[o[i]].push_back(i);
  57.     }
  58.     for (int i = 1; i <= n; i++) {
  59.         scanf("%d", &intend[i]);
  60.     }
  61.     int k;
  62.     scanf("%d", &k);
  63.     int cnt = 0;
  64.     int sz = ceil(sqrt(k) * 3.3);
  65.     for (int i = 1; i <= k; i++) {
  66.         cnt++;
  67.         scanf("%d%d%d", &s[cnt].l, &s[cnt].r, &s[cnt].x);
  68.         if (i % sz == 0 || i == k) {
  69.             for (int j = 1; j <= n; j++) {
  70.                 oldSum[j] = sum[j];
  71.             }
  72.             for (int j = 1; j <= cnt; j++) {
  73.                 add[s[j].l] += s[j].x;
  74.                 if (s[j].l <= s[j].r) {
  75.                     add[s[j].r + 1] -= s[j].x;
  76.                 }
  77.             }
  78.             long long curAdd = 0;
  79.             for (int j = 1; j <= m; j++) {
  80.                 curAdd += add[j];
  81.                 add[j] = 0;
  82.                 if (known[o[j]]) continue;
  83.                 sum[o[j]] += curAdd;
  84.             }
  85.             for (int j = 1; j <= cnt; j++) {
  86.                 if (s[j].l > s[j].r) {
  87.                     add[s[j].r + 1] -= s[j].x;
  88.                 }
  89.             }
  90.             curAdd += add[m + 1];
  91.             for (int j = 1; j <= m; j++) {
  92.                 curAdd += add[j];
  93.                 add[j] = 0;
  94.                 if (known[o[j]]) continue;
  95.                 sum[o[j]] += curAdd;
  96.             }
  97.             add[m + 1] = 0;
  98.             int x;
  99.             for (int j = 1; j <= n; j++) {
  100.                 if (known[j]) continue;
  101.                 if (sum[j] >= intend[j]) {
  102.                     known[j] = true;
  103.                     for (int u = 1; u <= cnt && ans[j] == 0; u++) {
  104.                         for (int y = 0; y < list[j].size(); y++) {
  105.                             x = list[j][y];
  106.                             if (s[u].l <= s[u].r)  {
  107.                                 if (x >= s[u].l && x <= s[u].r) {
  108.                                     oldSum[j] += s[u].x;
  109.                                 }
  110.                             }
  111.                             else if (s[u].l <= x || s[u].r >= x) {
  112.                                 oldSum[j] += s[u].x;
  113.                             }
  114.                             if (oldSum[j] >= intend[j]) {
  115.                                 ans[j] = i - cnt + u;
  116.                                 break;
  117.                             }
  118.                         }
  119.                     }
  120.                 }
  121.             }
  122.             cnt = 0;
  123.         }
  124.     }
  125.     for (int i = 1; i <= n; i++) {
  126.         if (ans[i] > 0) {
  127.             printf("%d\n", ans[i]);
  128.         }
  129.         else printf("NIE\n");
  130.     }
  131. }
  132.  
Runtime error #stdin #stdout 0.1s 22280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Gqriff
language:
C++14 (gcc 8.3)
created:
8 years 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!