oj.uz

Submission #736157

# Submission time Handle Problem Language Result Execution time Memory
736157 2023-05-05T09:09:49 Z marvinthang Index (COCI21_index) C++17
110 / 110
 1460 ms 143008 KB 
/******************************
*    author : @marvinthang    *
*    date : 10 / 02 / 2022    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
#define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }

const 		int MOD = 1e9 + 7;
const     double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const     int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const       int MAX = 2e5 + 5;

struct Node {

	Node *l, *r;
	int val;

	Node(Node *_l = nullptr, Node *_r = nullptr, int v = 0) {
		l = _l; r = _r; val = v;
	}

};

Node *versions[MAX];
const int oo = 1 << 18;

void build(Node *cur, int l = 1, int r = oo - 1) {
	if (l == r) return;
	int mid = l + r >> 1;
	cur -> l = new Node();
	build(cur -> l, l, mid);
	cur -> r = new Node();
	build(cur -> r, mid + 1, r);
}

void upgrade(Node *prev, Node *cur, int pos, int val, int l = 1, int r = oo - 1) {
	if (l > pos || r < pos) return;
	if (l == r) {
		cur -> val = prev -> val + val;
		return;
	}
	int mid = l + r >> 1;
	if (pos <= mid) {
		cur -> r = prev -> r;
		cur -> l = new Node();
		upgrade(prev -> l, cur -> l, pos, val, l, mid);
	} else {
		cur -> l = prev -> l;
		cur -> r = new Node();
		upgrade(prev -> r, cur -> r, pos, val, mid + 1, r);
	}
	cur -> val = cur -> l -> val + cur -> r -> val;
}

int get(Node *prev, Node *cur, int u, int l = 1, int r = oo - 1) {
	if (l > oo || r < u) return 0;
	if (u <= l) return cur -> val - prev -> val;
	int mid = l + r >> 1;
	return get(prev -> l, cur -> l, u, l, mid) + get(prev -> r, cur -> r, u, mid + 1, r);
}

int N, Q, A[MAX];

int main(void) {
    superspeed;
    file("coci2021_r6_index");
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; ++i) scanf("%d", A + i);
    versions[0] = new Node();
    build(versions[0]);
	for (int i = 1; i <= N; ++i) {
		versions[i] = new Node();
		upgrade(versions[i - 1], versions[i], A[i], 1);
	}
    while (Q--) {
    	int l, r; scanf("%d%d", &l, &r);
    	int low = 1, high = oo;
    	while (low <= high) {
    		int mid = low + high >> 1;
    		if (get(versions[l - 1], versions[r], mid) >= mid)
    			low = mid + 1;
    		else high = mid - 1;
    	}
    	printf("%d\n", high);
    }
    return 0;
}

Compilation message

index.cpp: In function 'void build(Node*, int, int)':
index.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  int mid = l + r >> 1;
      |            ~~^~~
index.cpp: In function 'void upgrade(Node*, Node*, int, int, int, int)':
index.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int mid = l + r >> 1;
      |            ~~^~~
index.cpp: In function 'int get(Node*, Node*, int, int, int)':
index.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int mid = l + r >> 1;
      |            ~~^~~
index.cpp: In function 'int main()':
index.cpp:87:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~
index.cpp:11:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("coci2021_r6_index");
      |     ^~~~
index.cpp:11:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("coci2021_r6_index");
      |     ^~~~
index.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d%d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~
index.cpp:76:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     for (int i = 1; i <= N; ++i) scanf("%d", A + i);
      |                                  ~~~~~^~~~~~~~~~~~~
index.cpp:84:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |      int l, r; scanf("%d%d", &l, &r);
      |                ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 17324 KB Output is correct
2 Correct 22 ms 17332 KB Output is correct
3 Correct 26 ms 17332 KB Output is correct
4 Correct 24 ms 17256 KB Output is correct
5 Correct 23 ms 17264 KB Output is correct
6 Correct 23 ms 17364 KB Output is correct
7 Correct 28 ms 17356 KB Output is correct
8 Correct 24 ms 17332 KB Output is correct
9 Correct 24 ms 17268 KB Output is correct
10 Correct 42 ms 17356 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 17324 KB Output is correct
2 Correct 22 ms 17332 KB Output is correct
3 Correct 26 ms 17332 KB Output is correct
4 Correct 24 ms 17256 KB Output is correct
5 Correct 23 ms 17264 KB Output is correct
6 Correct 23 ms 17364 KB Output is correct
7 Correct 28 ms 17356 KB Output is correct
8 Correct 24 ms 17332 KB Output is correct
9 Correct 24 ms 17268 KB Output is correct
10 Correct 42 ms 17356 KB Output is correct
11 Correct 266 ms 48184 KB Output is correct
12 Correct 284 ms 48140 KB Output is correct
13 Correct 252 ms 48256 KB Output is correct
14 Correct 246 ms 48096 KB Output is correct
15 Correct 248 ms 48184 KB Output is correct
16 Correct 249 ms 48160 KB Output is correct
17 Correct 247 ms 48188 KB Output is correct
18 Correct 244 ms 48108 KB Output is correct
19 Correct 264 ms 48108 KB Output is correct
20 Correct 253 ms 48164 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 17324 KB Output is correct
2 Correct 22 ms 17332 KB Output is correct
3 Correct 26 ms 17332 KB Output is correct
4 Correct 24 ms 17256 KB Output is correct
5 Correct 23 ms 17264 KB Output is correct
6 Correct 23 ms 17364 KB Output is correct
7 Correct 28 ms 17356 KB Output is correct
8 Correct 24 ms 17332 KB Output is correct
9 Correct 24 ms 17268 KB Output is correct
10 Correct 42 ms 17356 KB Output is correct
11 Correct 266 ms 48184 KB Output is correct
12 Correct 284 ms 48140 KB Output is correct
13 Correct 252 ms 48256 KB Output is correct
14 Correct 246 ms 48096 KB Output is correct
15 Correct 248 ms 48184 KB Output is correct
16 Correct 249 ms 48160 KB Output is correct
17 Correct 247 ms 48188 KB Output is correct
18 Correct 244 ms 48108 KB Output is correct
19 Correct 264 ms 48108 KB Output is correct
20 Correct 253 ms 48164 KB Output is correct
21 Correct 1278 ms 142848 KB Output is correct
22 Correct 1415 ms 142884 KB Output is correct
23 Correct 1324 ms 142964 KB Output is correct
24 Correct 1300 ms 142972 KB Output is correct
25 Correct 1260 ms 142876 KB Output is correct
26 Correct 1460 ms 143008 KB Output is correct
27 Correct 1342 ms 142888 KB Output is correct
28 Correct 1329 ms 142940 KB Output is correct
29 Correct 1192 ms 142924 KB Output is correct
30 Correct 1138 ms 142952 KB Output is correct