oj.uz

Submission #172117

# Submission time Handle Problem Language Result Execution time Memory
172117 2019-12-31T07:46:09 Z dennisstar Strange Device (APIO19_strange_device) C++11
20 / 100
 1556 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=1000000000000000000ll;
	else A*=B;
	for (int i=0; i<n; i++) {
		scanf("%lld %lld", &l, &r);
		if (r-l+1>=A) {
			printf("%lld\n", A);
			return 0;
		}
		else {
			r=(r-l)+l%A;
			l%=A;
			if (r>=A) {
				assert(r<2*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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 14 ms 3064 KB Output is correct
3 Correct 15 ms 3576 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 2808 KB Output is correct
17 Correct 81 ms 7656 KB Output is correct
18 Correct 2 ms 256 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

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 868 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 589 ms 996 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 782 ms 63760 KB Output is correct
3 Runtime error 1556 ms 524288 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 2 ms 356 KB Output is correct
2 Correct 782 ms 63760 KB Output is correct
3 Runtime error 1556 ms 524288 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 2 ms 356 KB Output is correct
2 Correct 782 ms 63760 KB Output is correct
3 Runtime error 1556 ms 524288 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 163 ms 41924 KB Output is correct
3 Correct 290 ms 98892 KB Output is correct
4 Runtime error 1471 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 376 KB Output is correct
2 Correct 14 ms 3064 KB Output is correct
3 Correct 15 ms 3576 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 2808 KB Output is correct
17 Correct 81 ms 7656 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 380 KB Output is correct
21 Correct 2 ms 296 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 4 ms 888 KB Output is correct
26 Correct 4 ms 868 KB Output is correct
27 Correct 4 ms 888 KB Output is correct
28 Correct 589 ms 996 KB Output is correct
29 Correct 2 ms 356 KB Output is correct
30 Correct 782 ms 63760 KB Output is correct
31 Runtime error 1556 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -