Submission #1199396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199396		randnt93	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	30 / 100	1095 ms	2444 KiB

foehn_phenomena

#include <stdio.h>
#include <stdlib.h>

#include <set>
#include <map>
#include <list>
#include <queue>
#include <bitset>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

#define int long long
#define uint unsigned int
#define inf ULLONG_MAX

const uint blksize = 2000;
struct block {
  uint s;
  int* a;
  int v, pv;
};

int calc(uint blkc, struct block* blocks, uint S, uint T) {
#ifdef __DEBUG
  for (uint x = 0; x < blkc; x++) {
    printf("Block ID: %llu\n", x);
    printf("\t%lld", blocks[x].a[0]);
    for (uint i = 1; i < blocks[x].s; i++)
      printf(" %lld", blocks[x].a[i]);
    printf("\n");
    printf("\tv = %lld, pv = %lld\n", blocks[x].v, blocks[x].pv);
  }
#endif

  int pv = blocks[0].pv;
  for (uint b = 1; b < blkc; b++) {
    pv += blocks[b].pv;
    int r = blocks[b].a[0] + blocks[b].v,
      l = blocks[b - 1].a[blocks[b - 1].s - 1] + blocks[b - 1].v;

    if (r > l)
      pv -= S * (r - l);
    else
      pv += T * (l - r);
  }

  return pv;
}

void update_block(struct block& block, uint S, uint T, uint l, uint r, int v) {
  if (l == 0 && r == block.s - 1) {
    block.v += v;
    return;
  }

  if (l == 0)
    block.a[l++] += v;
  for (; l <= r; l++)
    block.a[l] += v;

  l = 1, block.pv = 0;
  for (; l < block.s; l++) {
    if (block.a[l] > block.a[l - 1])
      block.pv -= S * (block.a[l] - block.a[l - 1]);
    else
      block.pv += T * (block.a[l - 1] - block.a[l]);
  }
}

signed main() {
  uint N, Q, S, T;
  scanf("%llu%llu%llu%llu", &N, &Q, &S, &T);

  const uint blkc = ((N + 1) / blksize) + ((N + 1) % blksize > 0);
  struct block blocks[blkc];

  uint n = N + 1;
  for (uint x = 0; x < blkc; x++) {
    blocks[x].s = min(blksize, n);
    blocks[x].a = (int*)malloc(blocks[x].s * sizeof(int));
    blocks[x].pv = 0, blocks[x].v = 0;

    scanf("%lld", &blocks[x].a[0]);
    for (uint i = 1; i < blocks[x].s; i++) {
      scanf("%lld", &blocks[x].a[i]);
      if (blocks[x].a[i] > blocks[x].a[i - 1])
        blocks[x].pv -= (int)S * (blocks[x].a[i] - blocks[x].a[i - 1]);
      else
        blocks[x].pv += (int)T * (blocks[x].a[i - 1] - blocks[x].a[i]);
    }
    n -= min(blksize, n);
  }

  while (Q--) {
    uint l, r; int v;
    scanf("%llu%llu%lld", &l, &r, &v);

    uint sbid = l / blksize;
    uint ebid = r / blksize;

    if (sbid == ebid)
      update_block(blocks[sbid], S, T, l % blksize, r % blksize, v);
    else {
      update_block(blocks[sbid++], S, T, l % blksize, blksize - 1, v);
      for (; sbid < ebid; sbid++)
        update_block(blocks[sbid], S, T, 0, blksize - 1, v);
      update_block(blocks[ebid], S, T, 0, r % blksize, v);
    }

    printf("%lld\n", calc(blkc, blocks, S, T));
  }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%llu%llu%llu%llu", &N, &Q, &S, &T);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%lld", &blocks[x].a[0]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:88:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |       scanf("%lld", &blocks[x].a[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%llu%llu%lld", &l, &r, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60