Language: C++

#define _STDIO_H

#include <cstdio>
#include <cstdint>
#include <cctype>
#include <climits>
#include <cinttypes>
#include <set>
#include <map>
#include <algorithm>
#include <vector>
#include <utility>

//#define fprintf(...) void(0)

int main() {
  intmax_t N;
  int M, K, D, S;
  scanf("%jd %d %d %d %d", &N, &M, &K, &D, &S);

  if (N > M)
    return !printf("%jd\n", intmax_t(K)*D);

  std::map<intmax_t, std::vector<std::pair<int, int>>> regi;
  for (int i=0; i<M; ++i) {
    int a, b;
    intmax_t c;
    scanf("%d %d %jd", &a, &b, &c);
    regi[c].emplace_back(a, a+b);
  }

  std::set<std::pair<int, int>> tsurai;
  for (const auto &pp: regi) {
    std::vector<std::pair<int, int>> cur;
    int P=0;
    int last=0;
    for (const auto &p: pp.second) {
      int s=p.first, e=p.second;
      if (P+last == s) {
        cur.emplace_back(s, s);
        P = 0;
      } else if (P+last < s) {
        cur.emplace_back(P+last, s);
        P = 0;
      } else {
        P -= s-last;
      }

      P += e-s;
      last = s;
    }
    cur.emplace_back(last+P, INT_MAX);
    for (const auto &p: cur)
      tsurai.insert(p);
  }

  std::vector<std::pair<int, int>> disjoint;
  for (const auto &p: tsurai) {
    if (disjoint.empty()) {
      disjoint.push_back(p);
      continue;
    }
    if (p.first <= disjoint.back().second) {
      disjoint.back().second = p.second;
    } else {
      disjoint.push_back(p);
    }
  }

  for (const auto &p: disjoint) {
    fprintf(stderr, "[%d, %d)\n", p.first, p.second);
  }

  int SS=S;
  for (int i=0; i<K; ++i) {
    S += D;
    fprintf(stderr, "> %d\n", S);
    size_t lb=0, ub=disjoint.size();
    while (ub-lb > 1) {
      size_t mid=(lb+ub)>>1;
      (S < disjoint[mid].second? lb:ub) = mid;
    }
    fprintf(stderr, "[%d, %d)\n", disjoint[lb].first, disjoint[lb].second);
    S = std::max(disjoint[lb].first, S);
    fprintf(stderr, "< %d\n\n", S);
    if (i+1 == K)
      return !printf("%d\n", S-SS);
  }
}



Compiler output:
In file included from a.cc:3:
/usr/include/c++/14/cstdio:98:11: error: 'FILE' has not been declared in '::'
   98 |   using ::FILE;
      |           ^~~~
/usr/include/c++/14/cstdio:99:11: error: 'fpos_t' has not been declared in '::'
   99 |   using ::fpos_t;
      |           ^~~~~~
/usr/include/c++/14/cstdio:101:11: error: 'clearerr' has not been declared in '::'
  101 |   using ::clearerr;
      |           ^~~~~~~~
/usr/include/c++/14/cstdio:102:11: error: 'fclose' has not been declared in '::'
  102 |   using ::fclose;
      |           ^~~~~~
/usr/include/c++/14/cstdio:103:11: error: 'feof' has not been declared in '::'
  103 |   using ::feof;
      |           ^~~~
/usr/include/c++/14/cstdio:104:11: error: 'ferror' has not been declared in '::'
  104 |   using ::ferror;
      |           ^~~~~~
/usr/include/c++/14/cstdio:105:11: error: 'fflush' has not been declared in '::'
  105 |   using ::fflush;
      |           ^~~~~~
/usr/include/c++/14/cstdio:106:11: error: 'fgetc' has not been declared in '::'
  106 |   using ::fgetc;
      |           ^~~~~
/usr/include/c++/14/cstdio:107:11: error: 'fgetpos' has not been declared in '::'
  107 |   using ::fgetpos;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:108:11: error: 'fgets' has not been declared in '::'
  108 |   using ::fgets;
      |           ^~~~~
/usr/include/c++/14/cstdio:109:11: error: 'fopen' has not been declared in '::'
  109 |   using ::fopen;
      |           ^~~~~
/usr/include/c++/14/cstdio:110:11: error: 'fprintf' has not been declared in '::'
  110 |   using ::fprintf;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:111:11: error: 'fputc' has not been declared in '::'
  111 |   using ::fputc;
      |           ^~~~~
/usr/include/c++/14/cstdio:112:11: error: 'fputs' has not been declared in '::'
  112 |   using ::fputs;
      |           ^~~~~
/usr/include/c++/14/cstdio:113:11: error: 'fread' has not been declared in '::'
  113 |   using ::fread;
      |           ^~~~~
/usr/include/c++/14/cstdio:114:11: error: 'freopen' has not been declared in '::'
  114 |   using ::freopen;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:115:11: error: 'fscanf' has not been declared in '::'
  115 |   using ::fscanf;
      |           ^~~~~~
/usr/include/c++/14/cstdio:116:11: error: 'fseek' has not been declared in '::'
  116 |   using ::fseek;
      |           ^~~~~
/usr/include/c++/14/cstdio:117:11: error: 'fsetpos' has not been declared in '::'
  117 |   using ::fsetpos;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:118:11: error: 'ftell' has not been declared in '::'
  118 |   using ::ftell;
      |           ^~~~~
/usr/include/c++/14/cstdio:119:11: error: 'fwrite' has not been declared in '::'
  119 |   using ::fwrite;
      |           ^~~~~~
/usr/include/c++/14/cstdio:120:11: error: 'getc' has not been declared in '::'
  120 |   using ::getc;
      |           ^~~~
/usr/include/c++/14/cstdio:121:11: error: 'getchar' has not been declared in '::'
  121 |   using ::getchar;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:126:11: error: 'perror' has not been declared in '::'
  126 |   using ::perror;
      |           ^~~~~~
/usr/include/c++/14/cstdio:127:11: error: 'printf' has not been declared in '::'
  127 |   using ::printf;
      |           ^~~~~~
/usr/include/c++/14/cstdio:128:11: error: 'putc' has not been declared in '::'
  128 |   using ::putc;
      |           ^~~~
/usr/include/c++/14/cstdio:129:11: error: 'putchar' has not been declared in '::'
  129 |   using ::putchar;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:130:11: error: 'puts' has not been declared in '::'
  130 |   using ::puts;
      |           ^~~~
/usr/include/c++/14/cstdio:131:11: error: 'remove' has not been declared in '::'
  131 |   using ::remove;
      |           ^~~~~~
/usr/include/c++/14/cstdio:132:11: error: 'rename' has not been declared in '::'
  132 |   using ::rename;
      |           ^~~~~~
/usr/include/c++/14/cstdio:133:11: error: 'rewind' has not been declared in '::'
  133 |   using ::rewind;
      |           ^~~~~~
/usr/include/c++/14/cstdio:134:11: error: 'scanf' has not been declared in '::'
  134 |   using ::scanf;
      |           ^~~~~
/usr/include/c++/14/cstdio:135:11: error: 'setbuf' has not been declared in '::'
  135 |   using ::setbuf;
      |           ^~~~~~
/usr/include/c++/14/cstdio:136:11: error: 'setvbuf' has not been declared in '::'
  136 |   using ::setvbuf;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:137:11: error: 'sprintf' has not been declared in '::'
  137 |   using ::sprintf;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:138:11: error: 'sscanf' has not been declared in '::'
  138 |   using ::sscanf;
      |           ^~~~~~
/usr/include/c++/14/cstdio:139:11: error: 'tmpfile' has not been declared in '::'
  139 |   using ::tmpfile;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:141:11: error: 'tmpnam' has not been declared in '::'
  141 |   using ::tmpnam;
      |           ^~~~~~
/usr/include/c++/14/cstdio:143:11: error: 'ungetc' has not been declared in '::'
  143 |   using ::ungetc;
      |           ^~~~~~
/usr/include/c++/14/cstdio:144:11: error: 'vfprintf' has not been declared in '::'
  144 |   using ::vfprintf;
      |           ^~~~~~~~
/usr/include/c++/14/cstdio:145:11: error: 'vprintf' has not been declared in '::'
  145 |   using ::vprintf;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:146:11: error: 'vsprintf' has not been declared in '::'
  146 |   using ::vsprintf;
      |           ^~~~~~~~
/usr/include/c++/14/cstdio:175:11: error: 'snprintf' has not been declared in '::'
  175 |   using ::snprintf;
      |           ^~~~~~~~
/usr/include/c++/14/cstdio:176:11: error: 'vfscanf' has not been declared in '::'
  176 |   using ::vfscanf;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:177:11: error: 'vscanf' has not been declared in '::'
  177 |   using ::vscanf;
      |           ^~~~~~
/usr/include/c++/14/cstdio:178:11: error: 'vsnprintf' has not been declared in '::'
  178 |   using ::vsnprintf;
      |           ^~~~~~~~~
/usr/include/c++/14/cstdio:179:11: error: 'vsscanf' has not been declared in '::'
  179 |   using ::vsscanf;
      |           ^~~~~~~
/usr/include/c++/14/cstdio:185:22: error: 'snprintf' has not been declared in '__gnu_cxx'
  185 |   using ::__gnu_cxx::snprintf;
      |                      ^~~~~~~~
/usr/include/c++/14/cstdio:186:22: error: 'vfscanf' has not been declared in '__gnu_cxx'
  186 |   using ::__gnu_cxx::vfscanf;
      |                      ^~~~~~~
/usr/include/c++/14/cstdio:187:22: error: 'vscanf' has not been declared in '__gnu_cxx'
  187 |   using ::__gnu_cxx::vscanf;
      |                      ^~~~~~
/usr/include/c++/14/cstdio:188:22: error: 'vsnprintf' has not been declared in '__gnu_cxx'
  188 |   using ::__gnu_cxx::vsnprintf;
      |                      ^~~~~~~~~
/usr/include/c++/14/cstdio:189:22: error: 'vsscanf' has not been declared in '__gnu_cxx'
  189 |   using ::__gnu_cxx::vsscanf;
      |                      ^~~~~~~
a.cc: In function 'int main()':
a.cc:19:3: error: 'scanf' was not declared in this scope
   19 |   scanf("%jd %d %d %d %d", &N, &M, &K, &D, &S);
      |   ^~~~~
a.cc:22:13: error: 'printf' was not declared in this scope
   22 |     return !printf("%jd\n", intmax_t(K)*D);
      |             ^~~~~~
a.cc:13:1: note: 'printf' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'
   12 | #include <utility>
  +++ |+#include <cstdio>
   13 | 
a.cc:71:13: error: 'stderr' was not declared in this scope
   71 |     fprintf(stderr, "[%d, %d)\n", p.first, p.second);
      |             ^~~~~~
a.cc:71:13: note: 'stderr' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'
a.cc:71:5: error: 'fprintf' was not declared in this scope
   71 |     fprintf(stderr, "[%d, %d)\n", p.first, p.second);
      |     ^~~~~~~
a.cc:77:13: error: 'stderr' was not declared in this scope
   77 |     fprintf(stderr, "> %d\n", S);
      |             ^~~~~~
a.cc:77:13: note: 'stderr' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'
a.cc:77:5: error: 'fprintf' was not declared in this scope
   77 |     fprintf(stderr, "> %d\n", S);
      |     ^~~~~~~
a.cc:87:15: error: 'printf' was not declared in this scope
   87 |       return !printf("%d\n", S-SS);
      |               ^~~~~~
a.cc:87:15: note: 'printf' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'