oj.uz

Submission #172118

# Submission time Handle Problem Language Result Execution time Memory
172118 2019-12-31T07:47:27 Z dennisstar Strange Device (APIO19_strange_device) C++11
15 / 100
 1538 ms 524292 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

struct seg {
	ll val;
	seg *l, *r;
	seg() {val=0, l=r=NULL;}
	void upd(ll s, ll e, ll fr, ll re) {
		if (fr>re||val==(re-fr+1)) return ;
		if (s<=fr&&re<=e) {val=(re-fr+1); return ;}
		ll md=(fr+re)/2;
		if (s<=md) {
			if (!l) l=new seg();
			l->upd(s, e, fr, md);
		}
		if (md+1<=e) {
			if (!r) r=new seg();
			r->upd(s, e, md+1, re);
		}
		val=(l?l->val:0)+(r?r->val:0);
	}
};
seg *root=new seg();

int n; ll A, B;
ll l, r;

int main() {
	scanf("%d %lld %lld", &n, &A, &B);
	A/=__gcd(A, B+1);
	if (1000000000000000000ll/B<=A) A=1000000000000000001ll;
	else A*=B;
	for (int i=0; i<n; i++) {
		scanf("%lld %lld", &l, &r); l--; r--;
		if (r-l+1>=A) {
			printf("%lld\n", A);
			return 0;
		}
		else {
			r=(r-l)+l%A;
			l%=A;
			if (r>=A) {
				root->upd(l, A-1, 0, A-1);
				root->upd(0, r-A, 0, A-1);
			}
			else root->upd(l, r, 0, A-1);
		}
	}
	printf("%lld\n", root->val);
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %lld", &n, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &l, &r); l--; r--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 12 ms 2632 KB Output is correct
3 Correct 15 ms 3192 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 0 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 1 ms 376 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 3 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 17 ms 2424 KB Output is correct
17 Correct 78 ms 6704 KB Output is correct
18 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 740 ms 352 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 777 ms 63020 KB Output is correct
3 Runtime error 1538 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 777 ms 63020 KB Output is correct
3 Runtime error 1538 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 777 ms 63020 KB Output is correct
3 Runtime error 1538 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 162 ms 41696 KB Output is correct
3 Correct 289 ms 98580 KB Output is correct
4 Runtime error 1459 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 12 ms 2632 KB Output is correct
3 Correct 15 ms 3192 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 0 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 1 ms 376 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 3 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 17 ms 2424 KB Output is correct
17 Correct 78 ms 6704 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 2 ms 380 KB Output isn't correct
22 Halted 0 ms 0 KB -