Submission #172118

#	Time	Username	Problem	Language	Result	Execution time	Memory
172118		dennisstar	Strange Device (APIO19_strange_device)	C++11	15 / 100	1538 ms	524292 KiB

strange_device

#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 (stderr)

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 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30