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.     memset(add, 0, sizeof(add));
  63.     memset(known, false, sizeof(known));
  64.     memset(a, 0, sizeof(a));
  65.     memset(sum, 0, sizeof(sum));
  66.     scanf("%d", &k);
  67.     int cnt = 0;
  68.     int sz = ceil(sqrt(k) * 3.3);
  69.     for (int i = 1; i <= k; i++) {
  70.         cnt++;
  71.         scanf("%d%d%d", &s[cnt].l, &s[cnt].r, &s[cnt].x);
  72.         if (i % sz == 0 || i == k) {
  73.             for (int j = 1; j <= n; j++) {
  74.                 oldSum[j] = sum[j];
  75.             }
  76.             for (int j = 1; j <= cnt; j++) {
  77.                 add[s[j].l] += s[j].x;
  78.                 if (s[j].l <= s[j].r) {
  79.                     add[s[j].r + 1] -= s[j].x;
  80.                 }
  81.             }
  82.             long long curAdd = 0;
  83.             for (int j = 1; j <= m; j++) {
  84.                 curAdd += add[j];
  85.                 add[j] = 0;
  86.                 if (known[o[j]]) continue;
  87.                 sum[o[j]] += curAdd;
  88.             }
  89.             for (int j = 1; j <= cnt; j++) {
  90.                 if (s[j].l > s[j].r) {
  91.                     add[s[j].r + 1] -= s[j].x;
  92.                 }
  93.             }
  94.             curAdd += add[m + 1];
  95.             for (int j = 1; j <= m; j++) {
  96.                 curAdd += add[j];
  97.                 add[j] = 0;
  98.                 if (known[o[j]]) continue;
  99.                 sum[o[j]] += curAdd;
  100.             }
  101.             add[m + 1] = 0;
  102.             int x;
  103.             for (int j = 1; j <= n; j++) {
  104.                 if (known[j]) continue;
  105.                 if (sum[j] >= intend[j]) {
  106.                     known[j] = true;
  107.                     for (int u = 1; u <= cnt && ans[j] == 0; u++) {
  108.                         for (int y = 0; y < list[j].size(); y++) {
  109.                             x = list[j][y];
  110.                             if (s[u].l <= s[u].r)  {
  111.                                 if (x >= s[u].l && x <= s[u].r) {
  112.                                     oldSum[j] += s[u].x;
  113.                                 }
  114.                             }
  115.                             else if (s[u].l <= x || s[u].r >= x) {
  116.                                 oldSum[j] += s[u].x;
  117.                             }
  118.                             if (oldSum[j] >= intend[j]) {
  119.                                 ans[j] = i - cnt + u;
  120.                                 break;
  121.                             }
  122.                         }
  123.                     }
  124.                 }
  125.             }
  126.             cnt = 0;
  127.         }
  128.     }
  129.     for (int i = 1; i <= n; i++) {
  130.         if (ans[i] > 0) {
  131.             printf("%d\n", ans[i]);
  132.         }
  133.         else printf("NIE\n");
  134.     }
  135. }
  136.  
Time limit exceeded #stdin #stdout 5s 19448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4yA440
problem METEORS, based on SPOJ submission 11963680 (C++ 4.3.2), 2014-07-17 10:34:48
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!