Submission #475829

#	Time	Username	Problem	Language	Result	Execution time	Memory
475829		maomao90	Progression (NOI20_progression)	C++17	0 / 100	1211 ms	149116 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(ll 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;
	}
	ll eval(ll x) {
		return m * x + c;
	}
};

#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(-LINF); ladd[u].reset(0);
}

ap join(ap l, ap r, int hlf) {
	ap res;
	res.reset(0);
	if (l.e + 1 != r.s) return res;
	if (l.e == l.s && r.e == r.s) {
		ll m = r.c - l.c;
		// l.c = m(l.s) + c
		ll c = l.c - m * l.s;
		l.m = r.m = m;
		l.c = r.c = c;
	} else if (l.e == l.s) {
		ll ex = r.eval(r.s - 1);
		if (l.c == ex) {
			l.m = r.m;
			l.c = r.c;
		}
	} else if (r.e == r.s) {
		ll ex = l.eval(l.e + 1);
		if (r.c == ex) {
			r.m = l.m;
			r.c = l.c;
		}
	}
	if (l.m == r.m && l.c == r.c) {
		res = {l.m, l.c, l.s, r.e};
	}
	if (hlf & 1) {
		ll ex = r.eval(r.s - 1);
		if (l.eval(r.s - 1) == ex) {
			mxto(res, {r.m, r.c, r.s - 1, r.e});
		}
	}
	if (hlf & 2) {
		ll ex = l.eval(l.e + 1);
		if (r.eval(l.e + 1) == ex) {
			mxto(res, {l.m, l.c, l.s, l.e + 1});
		}
	}
	return res;
}
void merge(ap* res, ap* lft, ap* rht) {
	res[0] = max(lft[0], max(lft[2], join(lft[2], rht[0], 2)));
	res[1] = max(rht[1], max(rht[2], join(lft[1], rht[2], 1)));
	res[3] = max(lft[3], max(rht[3], max(lft[1],
				   	max(rht[0], join(lft[1], rht[0], 3)))));
	res[2] = join(lft[2], rht[2], 0);
}

void init(int u = 1, int lo = 1, int hi = n) {
	lset[u].reset(-LINF); ladd[u].reset(0);
	REP (i, 0, 4) {
		v[u][i].reset(0);
	}
	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};
		if (s == e) {
			cap = {0, c, lo, hi};
		}
		lset[u] = cap;
		ladd[u].reset(0);
		debug("%d %d:\n", lo, hi);
		REP (i, 0, 4) {
			v[u][i] = cap;
			debug(" %d: %lld %lld %d %d\n", i, v[u][i].m, v[u][i].c, v[u][i].s, v[u][i].e);
		}
		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]);
	debug("%d %d:\n", lo, hi);
	REP (i, 0, 4) {
		debug(" %d: %lld %lld %d %d\n", i, v[u][i].m, v[u][i].c, v[u][i].s, v[u][i].e);
	}
}
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};
		if (s == e) {
			cap = {0, c, 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;
			int id = -1;
			REP (i, 0, 4) {
				if (mxto(ans, res[i].e - res[i].s + 1)) {
					id = i;
				}
			}
			assert(id != -1);
			debug("%d: %lld %d %d\n", id, res[id].c, res[id].s, res[id].e);
			printf("%d\n", ans);
		}
	}
	return 0;
}

/*
10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10

10 1
1 2 3 4 1 2 3 4 5 5
3 1 10

10 1
0 0 0 0 -2 -4 -6 -8 -10 -12
3 1 10
*/

Compilation message (stderr)

Progression.cpp: In function 'void propo(int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:65:2: note: in expansion of macro 'MLR'
   65 |  MLR;
      |  ^~~
Progression.cpp: In function 'void init(int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:146:3: note: in expansion of macro 'MLR'
  146 |   MLR;
      |   ^~~
Progression.cpp: In function 'void upset(int, int, int, int, int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:167:2: note: in expansion of macro 'MLR'
  167 |  MLR;
      |  ^~~
Progression.cpp: In function 'void incre(int, int, int, int, int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:193:2: note: in expansion of macro 'MLR'
  193 |  MLR;
      |  ^~~
Progression.cpp: In function 'void query(int, int, int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Progression.cpp:211:2: note: in expansion of macro 'MLR'
  211 |  MLR;
      |  ^~~
Progression.cpp: In function 'int main()':
Progression.cpp:234:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:237:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |   int d; scanf("%d", &d);
      |          ~~~~~^~~~~~~~~~
Progression.cpp:241:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |   int t; scanf("%d", &t);
      |          ~~~~~^~~~~~~~~~
Progression.cpp:243:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |    int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:246:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 |    int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:249:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  249 |    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