Submission #475815

#	Time	Username	Problem	Language	Result	Execution time	Memory
475815		maomao90	Progression (NOI20_progression)	C++17	0 / 100	1107 ms	158020 KiB

Progression

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005

int n, q;

struct ap {
	ll m, c;
   	int s, e;
	void reset(int x) {
		m = c = x;
		s = -1;
		e = -10;
	}
	bool operator< (const ap &o) const {
		return e - s < o.e - o.s;
	}
	ap& operator+= (const ap &o) {
		this -> m += o.m;
		this -> c += o.c;
		return *this;
	}
};

#define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
ap v[MAXN * 4][4]; // 0 is left, 1 is right, 2 is both, 3 is middle
ap lset[MAXN * 4], ladd[MAXN * 4];

void propo(int u, int lo, int hi) {
	if (lo == hi) return;
	MLR;
	if (lset[u].m != -LINF) {
		lset[lc].m = lset[u].m;
		lset[lc].c = lset[u].c;
		lset[rc].m = lset[u].m;
		lset[rc].c = lset[u].c;
		REP (i, 0, 4) {
			if (i == 2) {
			   	v[lc][i] = {lset[u].m, lset[u].c, lo, mid};
			   	v[rc][i] = {lset[u].m, lset[u].c, mid + 1, hi};
			} else {
				v[lc][i].reset(0);
				v[rc][i].reset(0);
			}
		}
	}
	if (ladd[u].m != 0 || ladd[u].c != 0) {
		ladd[lc] += ladd[u];
		ladd[rc] += ladd[u];
		REP (i, 0, 4) {
			v[lc][i] += ladd[u];
			v[rc][i] += ladd[u];
		}
	}
	lset[u].reset(-INF); ladd[u].reset(0);
}

ap join(ap& l, ap& r) {
	ap res;
	res.reset(0);
	if (l.m == r.m && l.c == r.c && l.e + 1 == r.s) {
		res = {l.m, l.c, l.s, r.e};
	}
	return res;
}
void merge(ap* res, ap* lft, ap* rht) {
	res[0] = max(lft[0], lft[2]);
	res[1] = max(rht[1], rht[2]);
	res[3] = max(lft[3], max(rht[3], max(lft[1],
				   	max(rht[0], join(lft[1], rht[0])))));
	res[2] = join(lft[2], rht[2]);
}

void init(int u = 1, int lo = 1, int hi = n) {
	lset[u].reset(-INF); ladd[u].reset(0);
	REP (i, 0, 4) {
		v[u][i].s = lo;
		v[u][i].e = hi;
	}
	if (lo != hi) {
		MLR;
		init(lc, lo, mid);
		init(rc, mid + 1, hi);
	}
}
void upset(int s, int e, int c, int m, int u = 1, int lo = 1, int hi = n) {
	if (lo >= s && hi <= e) {
		ap cap = {m, c - m * (s - 1), lo, hi};
		lset[u] = cap;
		ladd[u].reset(0);
		REP (i, 0, 4) {
			if (i == 2) {
			   	v[u][i] = cap;
			} else {
				v[u][i].reset(0);
			}
		}
		return;
	}
	propo(u, lo, hi);
	MLR;
	if (s <= mid) {
		upset(s, e, c, m, lc, lo, mid);
	}
	if (e > mid) {
		upset(s, e, c, m, rc, mid + 1, hi);
	}
	merge(v[u], v[lc], v[rc]);
}
void incre(int s, int e, int c, int m, int u = 1, int lo = 1, int hi = n) {
	if (lo >= s && hi <= e) {
		ap cap = {m, c - m * (s - 1), lo, hi};
		ladd[u] += cap;
		REP (i, 0, 4) {
			v[u][i] += cap;
		}
		return;
	}
	propo(u, lo, hi);
	MLR;
	if (s <= mid) {
		incre(s, e, c, m, lc, lo, mid);
	}
	if (e > mid) {
		incre(s, e, c, m, rc, mid + 1, hi);
	}
	merge(v[u], v[lc], v[rc]);
}
ap res[4];
void query(int s, int e, int u = 1, int lo = 1, int hi = n) {
	if (lo >= s && hi <= e) {
		REP (i, 0, 4) {
			res[i] = v[u][i];
		}
		return;
	}
	propo(u, lo, hi);
	MLR;
	if (e <= mid) {
		query(s, e, lc, lo, mid);
		return;
	} else if (s > mid) {
		query(s, e, rc, mid + 1, hi);
		return;
	} else {
		query(s, e, lc, lo, mid);
		ap lft[4];
		REP (i, 0, 4) {
			lft[i] = res[i];
		}
		query(s, e, rc, mid + 1, hi);
		ap rht[4];
		REP (i, 0, 4) {
			rht[i] = res[i];
		}
		merge(res, lft, rht);
	}
}

int main() {
	scanf("%d%d", &n, &q);
	init();
	REP (i, 1, n + 1) {
		int d; scanf("%d", &d);
		upset(i, i, d, 0);
	}
	while (q--) {
		int t; scanf("%d", &t);
		if (t == 1) {
			int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
			incre(l, r, s, c);
		} else if (t == 2) {
			int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
			upset(l, r, s, c);
		} else {
			int l, r; scanf("%d%d", &l, &r);
			query(l, r);
			int ans = 0;
			REP (i, 0, 4) {
				mxto(ans, res[i].e - res[i].s + 1);
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

Compilation message (stderr)

Progression.cpp: In function 'void propo(int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:62:2: note: in expansion of macro 'MLR'
   62 |  MLR;
      |  ^~~
Progression.cpp: In function 'void init(int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:112:3: note: in expansion of macro 'MLR'
  112 |   MLR;
      |   ^~~
Progression.cpp: In function 'void upset(int, int, int, int, int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:132:2: note: in expansion of macro 'MLR'
  132 |  MLR;
      |  ^~~
Progression.cpp: In function 'void incre(int, int, int, int, int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:151:2: note: in expansion of macro 'MLR'
  151 |  MLR;
      |  ^~~
Progression.cpp: In function 'void query(int, int, int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:169:2: note: in expansion of macro 'MLR'
  169 |  MLR;
      |  ^~~
Progression.cpp: In function 'int main()':
Progression.cpp:192:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:195:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |   int d; scanf("%d", &d);
      |          ~~~~~^~~~~~~~~~
Progression.cpp:199:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |   int t; scanf("%d", &t);
      |          ~~~~~^~~~~~~~~~
Progression.cpp:201:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |    int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:204:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |    int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:207:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |    int l, r; scanf("%d%d", &l, &r);
      |              ~~~~~^~~~~~~~~~~~~~~~

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