oj.uz

Submission #302164

# Submission time Handle Problem Language Result Execution time Memory
302164 2020-09-18T13:48:05 Z edenooo 역사적 조사 (JOI14_historical) C++17
15 / 100
 4000 ms 4968 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define INF 1234567890
#define ll long long

inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
	if (pow == 0) {
		return 0;
	}
	int hpow = 1 << (pow-1);
	int seg = (x < hpow) ? (
		(y < hpow) ? 0 : 3
	) : (
		(y < hpow) ? 1 : 2
	);
	seg = (seg + rotate) & 3;
	const int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	int64_t subSquareSize = int64_t(1) << (2*pow - 2);
	int64_t ans = seg * subSquareSize;
	int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
	return ans;
}
 
struct Node {
	int l, r, i;
	int64_t ord;
 
	inline void calcOrder() {
		ord = gilbertOrder(l, r, 17, 0);
	}
	bool operator<(const Node &n) {
		return ord < n.ord;
	}
};

const int SZ = 131072;
int N, Q;
int A[100101], B[100101];
ll res[100101], seg[270000];
vector<Node> q;
priority_queue<ll> pq, del;
vector<int> com;

void Update(int n, int val) // 0-based
{
	n += SZ; seg[n] += val;
	for(n>>=1; n; n>>=1) seg[n] = max(seg[n<<1], seg[n<<1|1]);
}

int main()
{
	scanf("%d %d", &N, &Q);
	for(int i=1; i<=N; i++)
	{
		scanf("%d", &A[i]);
		com.push_back(A[i]);
	}
	// 좌표 압축
	sort(com.begin(), com.end());
	com.erase(unique(com.begin(), com.end()), com.end());
	for(int i=1; i<=N; i++)
		B[i] = lower_bound(com.begin(), com.end(), A[i]) - com.begin();

	// 오프라인 쿼리
	for(int i=1; i<=Q; i++)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		q.push_back({l, r, i});
	}
	sort(q.begin(), q.end());

	// MO's
	int l = 1, r = 0; // [l, r]
	for(int i=0; i<q.size(); i++)
	{
		int nl = q[i].l, nr = q[i].r, idx = q[i].i;
		while(r < nr)
		{
			r++;
			Update(B[r], A[r]);
		}
		while(l < nl)
		{
			Update(B[l], -A[l]);
			l++;
		}
		while(nl < l)
		{
			l--;
			Update(B[l], A[l]);
		}
		while(nr < r)
		{
			Update(B[r], -A[r]);
			r--;
		}

		res[idx] = seg[1];
	}

	for(int i=1; i<=Q; i++)
		printf("%lld\n", res[i]);
	return 0;
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=0; i<q.size(); i++)
      |               ~^~~~~~~~~
historic.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d %d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~
historic.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 416 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 19 ms 384 KB Output is correct
19 Correct 75 ms 512 KB Output is correct
20 Correct 285 ms 640 KB Output is correct
21 Correct 705 ms 728 KB Output is correct
22 Correct 692 ms 936 KB Output is correct
23 Correct 746 ms 728 KB Output is correct
24 Correct 791 ms 796 KB Output is correct
25 Correct 718 ms 976 KB Output is correct
26 Correct 708 ms 820 KB Output is correct
27 Correct 700 ms 864 KB Output is correct
28 Correct 699 ms 804 KB Output is correct
29 Correct 697 ms 932 KB Output is correct
30 Correct 701 ms 796 KB Output is correct
31 Correct 726 ms 796 KB Output is correct
32 Correct 994 ms 848 KB Output is correct
33 Correct 676 ms 848 KB Output is correct
34 Correct 695 ms 848 KB Output is correct
35 Correct 714 ms 848 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 59 ms 504 KB Output is correct
6 Correct 23 ms 384 KB Output is correct
7 Correct 40 ms 632 KB Output is correct
8 Correct 15 ms 640 KB Output is correct
9 Correct 108 ms 896 KB Output is correct
10 Correct 852 ms 1148 KB Output is correct
11 Execution timed out 4094 ms 4968 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 416 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 19 ms 384 KB Output is correct
19 Correct 75 ms 512 KB Output is correct
20 Correct 285 ms 640 KB Output is correct
21 Correct 705 ms 728 KB Output is correct
22 Correct 692 ms 936 KB Output is correct
23 Correct 746 ms 728 KB Output is correct
24 Correct 791 ms 796 KB Output is correct
25 Correct 718 ms 976 KB Output is correct
26 Correct 708 ms 820 KB Output is correct
27 Correct 700 ms 864 KB Output is correct
28 Correct 699 ms 804 KB Output is correct
29 Correct 697 ms 932 KB Output is correct
30 Correct 701 ms 796 KB Output is correct
31 Correct 726 ms 796 KB Output is correct
32 Correct 994 ms 848 KB Output is correct
33 Correct 676 ms 848 KB Output is correct
34 Correct 695 ms 848 KB Output is correct
35 Correct 714 ms 848 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 4 ms 384 KB Output is correct
40 Correct 59 ms 504 KB Output is correct
41 Correct 23 ms 384 KB Output is correct
42 Correct 40 ms 632 KB Output is correct
43 Correct 15 ms 640 KB Output is correct
44 Correct 108 ms 896 KB Output is correct
45 Correct 852 ms 1148 KB Output is correct
46 Execution timed out 4094 ms 4968 KB Time limit exceeded
47 Halted 0 ms 0 KB -