Submission #261324

#	Time	Username	Problem	Language	Result	Execution time	Memory
261324		Nightlight	Progression (NOI20_progression)	C++14	100 / 100	1752 ms	69368 KiB

Progression

#include <bits/stdc++.h>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
using namespace std;

const long long INF = 2e18;
//segtree nyimpen selisih antara D[i] dan D[i + 1]

struct node {
  int best;
  long long l, r, sum;
  int r_sz, l_sz;
};

int N, Q;
int D[300005];
node tree[1200005];
long long lazy1[1200005];//nambah
long long lazy2[1200005];//ubah

inline void merge(node &now, node le, node ri) {
  now.best = max(le.best, ri.best);
  now.sum = le.sum + ri.sum;
  if(le.l_sz == -1 && ri.l_sz == -1) {
    if(le.r == ri.r) {
      now.r = le.r;
      now.r_sz =  le.r_sz + ri.r_sz;
      now.l_sz = -1;
    }else {
      now.l = le.r;
      now.l_sz = le.r_sz;
      now.r = ri.r;
      now.r_sz = ri.r_sz;
    }
  }else if(le.l_sz == -1) {
    if(le.r == ri.l) {
      now.l = le.r;
      now.l_sz = le.r_sz + ri.l_sz;
    }else {
      now.best = max(now.best, ri.l_sz);
      now.l = le.r;
      now.l_sz = le.r_sz;
    }
    now.r = ri.r;
    now.r_sz = ri.r_sz;
  }else if(ri.l_sz == -1) {
    if(le.r == ri.r) {
      now.r = ri.r;
      now.r_sz = le.r_sz + ri.r_sz;
    }else {
      now.best = max(now.best, le.r_sz);
      now.r = ri.r;
      now.r_sz = ri.r_sz;
    }
    now.l = le.l;
    now.l_sz = le.l_sz;
  }else {
    if(le.r == ri.l) {
      now.best = max(now.best, le.r_sz + ri.l_sz);
    }else {
      now.best = max(now.best, max(le.r_sz, ri.l_sz));
    }

    now.l = le.l;
    now.l_sz = le.l_sz;
    now.r = ri.r;
    now.r_sz = ri.r_sz;
  }
}

void build(int n, int l, int r) {
  lazy2[n] = INF;
  if(l == r) {
    tree[n].best = 1;
    tree[n].l_sz = -1;
    tree[n].r_sz = 1;
    tree[n].r = tree[n].sum = D[l + 1] - D[l];
//    cout << n <<  ": " << tree[n].r << "\n";
    return;
  }
  int mid = (l + r) >> 1;
  build(L(n), l, mid);
  build(R(n), mid + 1, r);
  merge(tree[n], tree[L(n)], tree[R(n)]);/*
  cout << l << " - " << r << "\n";
  cout << tree[n].best << "\n";
  cout << tree[n].l << " -> " << tree[n].l_sz << "\n";
  cout << tree[n].r << " -> " << tree[n].r_sz << "\n\n";*/
}

void unlazy(int n, int l, int r) {
  if(lazy2[n] != INF) {
    tree[n].l_sz = -1;
    tree[n].r_sz = r - l + 1;
    tree[n].r = lazy2[n];
    tree[n].sum = lazy2[n] * (r - l + 1);

    if(l != r) {
      if(lazy1[L(n)]) lazy1[L(n)] = 0;
      if(lazy1[R(n)]) lazy1[R(n)] = 0;
      lazy2[L(n)] = lazy2[n];
      lazy2[R(n)] = lazy2[n];
    }
    lazy2[n] = INF;
  }

  if(lazy1[n]) {
    tree[n].l += lazy1[n];
    tree[n].r += lazy1[n];
    tree[n].sum += lazy1[n] * (r - l + 1);

    if(l != r) {
      lazy1[L(n)] += lazy1[n];
      lazy1[R(n)] += lazy1[n];
    }
    lazy1[n] = 0;
  }
}

void trans(int n, int l, int r) {
  unlazy(n, l, r);
  if(l == r) {
    cout << tree[n].r << " ";
    return;
  }
  int mid = (l + r) >> 1;
  trans(L(n), l, mid);
  trans(R(n), mid + 1, r);
}

void trans() {trans(1, 0, N); cout << "\n";}

//update nambah
void update1(int n, int l, int r, int ql, int qr, int val) {
  unlazy(n, l, r);
  if(qr < l || r < ql) return;
  if(ql <= l && r <= qr) {
    lazy1[n] += val;
    unlazy(n, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update1(L(n), l, mid, ql, qr, val);
  update1(R(n), mid + 1, r, ql, qr, val);
  merge(tree[n], tree[L(n)], tree[R(n)]);
}

void update1(int ql, int qr, int val) {update1(1, 0, N, ql, qr, val);}

void update2(int n, int l, int r, int ql, int qr, int val) {
  unlazy(n, l, r);
  if(qr < l || r < ql) return;
  if(ql <= l && r <= qr) {
    lazy2[n] = val;
    lazy1[n] = 0;
    unlazy(n, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update2(L(n), l, mid, ql, qr, val);
  update2(R(n), mid + 1, r, ql, qr, val);
  merge(tree[n], tree[L(n)], tree[R(n)]);
}

void update2(int ql, int qr, int val) {update2(1, 0, N, ql, qr, val);}

node res;
long long res_sum;
long long sumL, sumR;

void sumq(int n, int l, int r, int ql, int qr) {
  unlazy(n, l, r);
  if(ql <= l && r <= qr) {
    res_sum += tree[n].sum;
    return;
  }
  int mid = (l + r) >> 1;
  if(ql <= mid) sumq(L(n), l, mid, ql, qr);
  if(qr > mid) sumq(R(n), mid + 1, r, ql, qr);
}

void sumq(int ql, int qr) {
  res_sum = 0;
  if(ql > qr) return;
  sumq(1, 0, N, ql, qr);
}

void query(int n, int l, int r, int ql, int qr) {
  unlazy(n, l, r);
  if(ql <= l && r <= qr) {
    merge(res, res, tree[n]);
//    cout << tree[n].r << " " << tree[n].r_sz << "\n";
    return;
  }
  int mid = (l + r) >> 1;
  if(ql <= mid) query(L(n), l, mid, ql, qr);
  if(qr > mid) query(R(n), mid + 1, r, ql, qr);
}

void query(int ql, int qr) {
  res.best = 0;
  res.l_sz = -1;
  res.r = INF;
  res.r_sz = 0;
  query(1, 0, N, ql, qr);
  res.best = max(res.best, res.r_sz);
}

int main() {  
  scanf("%d %d", &N, &Q);
  for(int i = 1; i <= N; i++) {
    scanf("%d", &D[i]);
  }
  build(1, 0, N);
//  cout << "\n";
  int ty, l, r, s;
  long long c;
//  trans();
  while(Q--) {
    scanf("%d", &ty);
    if(ty == 1) {
      scanf("%d %d %d %lld", &l, &r, &s, &c);
      update1(l - 1, l - 1, s);
      if(l < r) {
        update1(l, r - 1, c);
      }
      update1(r, r, -((r - l) * c + s));
//      trans();
    }else if(ty == 2) {
      scanf("%d %d %d %lld", &l, &r, &s, &c);
      sumq(0, l - 2);
      sumL = res_sum;
      sumq(0, r);
      sumR = res_sum;
//      cout << s - sumL << " " << sumR << "\n";
      update2(l - 1, l - 1, s - sumL);
//      trans();
      if(l < r) {
        update2(l, r - 1, c);
      }
      update2(r, r, sumR - ((r - l) * c + s));
//      trans();
    }else {
      scanf("%d %d", &l, &r);
      if(r - l > 1) {
        query(l, r - 1);
        printf("%d\n", res.best + 1);
//        cout << res.best << " " << res.r << "\n";
      }else printf("%d\n", r - l + 1);
    }
  }
  cin >> N;
} 

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:210:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &Q);
   ~~~~~^~~~~~~~~~~~~~~~~
Progression.cpp:212:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &D[i]);
     ~~~~~^~~~~~~~~~~~~
Progression.cpp:220:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ty);
     ~~~~~^~~~~~~~~~~
Progression.cpp:222:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %lld", &l, &r, &s, &c);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:230:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %lld", &l, &r, &s, &c);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:244:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &l, &r);
       ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17