oj.uz

Submission #681607

# Submission time Handle Problem Language Result Execution time Memory
681607 2023-01-13T13:01:58 Z MilosMilutinovic Progression (NOI20_progression) C++14
0 / 100
 3000 ms 41272 KB 
#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 == l.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 << 22);
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];
	}
	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);
}

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]);
	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;
}

/*
4 3
1 2
2 3
3 4
*/

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d", &d[i]);
      |   ~~~~~^~~~~~~~~~~~~
Progression.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d", &op);
      |   ~~~~~^~~~~~~~~~~
Progression.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 36680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 41272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 36688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 41272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 36680 KB Time limit exceeded
2 Halted 0 ms 0 KB -