Submission #681618

#	Time	Username	Problem	Language	Result	Execution time	Memory
681618		MilosMilutinovic	Progression (NOI20_progression)	C++14	35 / 100	244 ms	41916 KiB

Progression

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

typedef long long ll;

const int N = 300300;
int n, q;
int d[N];

struct Node {
	int mx, len, L, R;
	ll lval, rval;

	Node() {}
};
Node const operator + (Node l, Node r) {
	Node res;
	res.lval = l.lval;
	res.rval = r.rval;
	res.L = l.L + (l.L == l.len && r.lval == l.rval ? r.L : 0);
	res.R = r.R + (r.R == r.len && l.rval == r.lval ? l.R : 0);
	res.mx = max({l.mx, r.mx, res.L, res.R});
	if (l.rval == r.lval)
		res.mx = max(res.mx, l.R + r.L);
	res.len = l.len + r.len;
	return res;
}
const int M = (1 << 21);
Node tree[M];
void build(int p, int l, int r) {
	if (l == r) {
		tree[p].lval = d[r + 1] - d[r];
		tree[p].rval = d[r + 1] - d[r];
		tree[p].mx = 1;
		tree[p].len = r - l + 1;
		tree[p].L = 1;
		tree[p].R = 1;
		return;
	}
	int mid = (l + r) / 2;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
	tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
Node query(int p, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
//		printf("SEG = [%d,%d]\n", l, r);
		return tree[p];
	}
	if (l > qr || r < ql || l > r || ql > qr) {
		exit(0);
	}
	int mid = (l + r) / 2;
	if (qr <= mid)
		return query(p * 2, l, mid, ql, qr);
	else if (ql >= mid + 1)
		return query(p * 2 + 1, mid + 1, r, ql, qr);
	else
		return query(p * 2, l, mid, ql, qr) + query(p * 2 + 1, mid + 1, r, ql, qr);
}

void solveSTUPIDcase() {
	while(q--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int l, r, s, c;
			scanf("%d%d%d%d", &l, &r, &s, &c);
		} else if (op == 2) {
			int l, r, s, c;
			scanf("%d%d%d%d", &l, &r, &s, &c);
		} else if (op == 3) {
			int l, r;
			scanf("%d%d", &l, &r);
			printf("1\n");
		}
	}
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", &d[i]);
	if (n == 1) {
		solveSTUPIDcase();
		return 0;
	}
	build(1, 1, n - 1);
	while(q--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {

		} else if (op == 2) {
		} else {
			int l, r;
			scanf("%d%d", &l, &r);
			--r;
			if (l > r) {
				printf("%d\n", 1);
				continue;
			}
			printf("%d\n", query(1, 1, n - 1, l, r).mx + 1);
		}
	}
	return 0;
}

Compilation message (stderr)

Progression.cpp: In function 'void solveSTUPIDcase()':
Progression.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d", &op);
      |   ~~~~~^~~~~~~~~~~
Progression.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |    scanf("%d%d%d%d", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |    scanf("%d%d%d%d", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp: In function 'int main()':
Progression.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d", &d[i]);
      |   ~~~~~^~~~~~~~~~~~~
Progression.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   scanf("%d", &op);
      |   ~~~~~^~~~~~~~~~~
Progression.cpp:120:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~

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