Submission #1100638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100638		vjudge1	Strange Device (APIO19_strange_device)	C++17	20 / 100	1309 ms	524288 KiB

strange_device

//#pragma optimize ("g",on)
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define ll long long
#define db double
#define ld long double
#define pb push_back
#define pf push_front
#define ppb pop_back()
#define ppf pop_front()
#define len(x) (int)x.size()
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define vvi vector<vi>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mii map<int,int>
#define y1 u_will_not_notice_this15
#define hash u_will_not_notice_this
#define tm (tl+tr>>1)
#define ls v<<1,tl,tm
#define rs v<<1|1,tm+1,tr
#define pii pair<int,int>
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define str string
#define ins insert
#define elif else if
using namespace std;
using namespace __gnu_pbds;
const int maxn=1e6+5,mod=1e9+7,inf=1e18,bir=1,nol=0;
const bool TEST=0;
const str tch="+abcdefghijklmnopqrstuvwxyz",Tch="+ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const str Monday_14_10_24[5]={"NO\n","YES\n","-1\n","0\n","1\n"};
void at(int ok){cout<<Monday_14_10_24[ok];}
bool bit(int mask,int i){return ((bir<<i)&mask);}
int gcd(int a,int b){while(b){if(a>b) swap(a,b);b%=a;}return a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int rnd(){return (rand()<<15)^rand();}
int bpm(int a,int b){a%=mod;if(b==0) return 1;if(b&1)return bpm(a,b-1)*a%mod;int x=bpm(a,b>>1);return x*x%mod;}
int bp(int a,int b){if(b==0) return 1;if(b&1)return bp(a,b-1)*a;int x=bp(a,b>>1);return x*x;}
//CODE STARTS HERE:
//don't get stuck on one aproach
int n,a,b,l[maxn],r[maxn],lcc,timer=1,t[40*maxn],lv[40*maxn],rv[40*maxn],used[maxn*40];
void upd(int l,int r,int v=1,int tl=1,int tr=inf){
	if(t[v]==tr-tl+1)return;
	if(l>tr||tl>r)return;
	if(l<=tl&&tr<=r){
		t[v]=tr-tl+1;return;
	}
	if(!lv[v])lv[v]=++timer;
	if(!rv[v])rv[v]=++timer;
	upd(l,r,lv[v],tl,tm),upd(l,r,rv[v],tm+1,tr);
	t[v]=t[lv[v]]+t[rv[v]];
}
void updq(int l,int r){
	upd(l+1,r+1);
}
void whyareucopying(){
	cin>>n>>a>>b;
	int s=0;
	for(int i=1;i<=n;i++)cin>>l[i]>>r[i],s+=r[i]-l[i]+1;
	if(a/gcd(a,b+1)>1e18/b){
		cout<<s<<'\n';return;
	}
	lcc=a*b/gcd(a,b+1);
	for(int i=1;i<=n;i++){
		if(r[i]-l[i]+1>=lcc)updq(0,lcc-1);
		elif(l[i]%lcc<=r[i]%lcc)updq(l[i]%lcc,r[i]%lcc);
		else updq(l[i]%lcc,lcc-1),updq(0,r[i]%lcc);
	}
	cout<<t[1]<<'\n';
}
signed main(){
//	freopen("txt.in","r",stdin),freopen("txt.out","w",stdout);
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(time(0));
	int T=1;
	if(TEST)cin>>T;
	for(int i=1;i<=T;i++){
//		cout<<"Case "<<i<<": ";
		whyareucopying();
	}
}

Compilation message (stderr)

strange_device.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
strange_device.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 | #define tm (tl+tr>>1)
      |             ~~^~~
strange_device.cpp:58:19: note: in expansion of macro 'tm'
   58 |  upd(l,r,lv[v],tl,tm),upd(l,r,rv[v],tm+1,tr);
      |                   ^~
strange_device.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 | #define tm (tl+tr>>1)
      |             ~~^~~
strange_device.cpp:58:37: note: in expansion of macro 'tm'
   58 |  upd(l,r,lv[v],tl,tm),upd(l,r,rv[v],tm+1,tr);
      |                                     ^~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 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