oj.uz

Submission #681618

# Submission time Handle Problem Language Result Execution time Memory
681618 2023-01-13T13:10:53 Z MilosMilutinovic Progression (NOI20_progression) C++14
35 / 100
 244 ms 41916 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 == 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

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.0

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

Subtask #2
0 / 15.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 35324 KB Output is correct
2 Correct 95 ms 884 KB Output is correct
3 Correct 92 ms 856 KB Output is correct
4 Correct 88 ms 836 KB Output is correct
5 Correct 98 ms 964 KB Output is correct
6 Correct 98 ms 892 KB Output is correct
7 Correct 99 ms 844 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 240 ms 39976 KB Output is correct
12 Correct 211 ms 41420 KB Output is correct
13 Correct 237 ms 39948 KB Output is correct
14 Correct 235 ms 39968 KB Output is correct
15 Correct 215 ms 41336 KB Output is correct
16 Correct 238 ms 41888 KB Output is correct
17 Correct 239 ms 41916 KB Output is correct
18 Correct 244 ms 41912 KB Output is correct
19 Correct 206 ms 41228 KB Output is correct
20 Correct 225 ms 41256 KB Output is correct
21 Correct 212 ms 41300 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 35324 KB Output is correct
2 Correct 95 ms 884 KB Output is correct
3 Correct 92 ms 856 KB Output is correct
4 Correct 88 ms 836 KB Output is correct
5 Correct 98 ms 964 KB Output is correct
6 Correct 98 ms 892 KB Output is correct
7 Correct 99 ms 844 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 240 ms 39976 KB Output is correct
12 Correct 211 ms 41420 KB Output is correct
13 Correct 237 ms 39948 KB Output is correct
14 Correct 235 ms 39968 KB Output is correct
15 Correct 215 ms 41336 KB Output is correct
16 Correct 238 ms 41888 KB Output is correct
17 Correct 239 ms 41916 KB Output is correct
18 Correct 244 ms 41912 KB Output is correct
19 Correct 206 ms 41228 KB Output is correct
20 Correct 225 ms 41256 KB Output is correct
21 Correct 212 ms 41300 KB Output is correct
22 Incorrect 50 ms 36812 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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