oj.uz

Submission #1100653

# Submission time Handle Problem Language Result Execution time Memory
1100653 2024-10-14T11:42:52 Z vjudge1 Strange Device (APIO19_strange_device) C++17
15 / 100
 1140 ms 524288 KB 
//#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+3020,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[53*maxn],lv[53*maxn],rv[53*maxn];
void upd(int l,int r,int v=1,int tl=1,int tr=lcc+20){
	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(!(l>tm||tl>r)&&t[lv[v]]<tm-tl+1){
		if(!lv[v])lv[v]=++timer;
		upd(l,r,lv[v],tl,tm);
	}
	if(!(l>tr||tm+1>r)&&t[rv[v]]<tr-tm){
		if(!rv[v])rv[v]=++timer;
		upd(l,r,rv[v],tm+1,tr);
	}
	t[v]=t[lv[v]]+t[rv[v]];
}
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)>inf/b){
		cout<<s<<'\n';return;
	}
	lcc=a/gcd(a,b+1)*b;
	if(lcc>inf){
		cout<<s<<'\n';return;
	}
	set<pii>st;
	for(int i=1;i<=n;i++){
		if(l[i]%lcc<=r[i]%lcc)st.ins({l[i]%lcc+1,r[i]%lcc+1});
		else st.ins({1,r[i]%lcc+1}),st.ins({l[i]%lcc+1,lcc});
	}
	mii mp;
	for(auto [l,r]:st)mp[l]=r;	
	for(auto [l,r]:mp)upd(l,r);
	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

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:56:9: note: in expansion of macro 'tm'
   56 |  if(!(l>tm||tl>r)&&t[lv[v]]<tm-tl+1){
      |         ^~
strange_device.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 | #define tm (tl+tr>>1)
      |             ~~^~~
strange_device.cpp:56:29: note: in expansion of macro 'tm'
   56 |  if(!(l>tm||tl>r)&&t[lv[v]]<tm-tl+1){
      |                             ^~
strange_device.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 | #define tm (tl+tr>>1)
      |             ~~^~~
strange_device.cpp:58:20: note: in expansion of macro 'tm'
   58 |   upd(l,r,lv[v],tl,tm);
      |                    ^~
strange_device.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 | #define tm (tl+tr>>1)
      |             ~~^~~
strange_device.cpp:60:13: note: in expansion of macro 'tm'
   60 |  if(!(l>tr||tm+1>r)&&t[rv[v]]<tr-tm){
      |             ^~
strange_device.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 | #define tm (tl+tr>>1)
      |             ~~^~~
strange_device.cpp:60:34: note: in expansion of macro 'tm'
   60 |  if(!(l>tr||tm+1>r)&&t[rv[v]]<tr-tm){
      |                                  ^~
strange_device.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 | #define tm (tl+tr>>1)
      |             ~~^~~
strange_device.cpp:62:17: note: in expansion of macro 'tm'
   62 |   upd(l,r,rv[v],tm+1,tr);
      |                 ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 9 ms 7504 KB Output is correct
3 Correct 9 ms 8272 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4600 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 1 ms 4432 KB Output is correct
13 Correct 1 ms 4600 KB Output is correct
14 Correct 1 ms 4432 KB Output is correct
15 Correct 2 ms 4432 KB Output is correct
16 Correct 11 ms 7248 KB Output is correct
17 Correct 79 ms 21812 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Incorrect 1 ms 4432 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 2 ms 5172 KB Output is correct
5 Correct 171 ms 16604 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 760 ms 188784 KB Output is correct
3 Runtime error 1063 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 760 ms 188784 KB Output is correct
3 Runtime error 1063 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 760 ms 188784 KB Output is correct
3 Runtime error 1063 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 105 ms 51252 KB Output is correct
3 Correct 155 ms 93768 KB Output is correct
4 Runtime error 1140 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 9 ms 7504 KB Output is correct
3 Correct 9 ms 8272 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4600 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 1 ms 4432 KB Output is correct
13 Correct 1 ms 4600 KB Output is correct
14 Correct 1 ms 4432 KB Output is correct
15 Correct 2 ms 4432 KB Output is correct
16 Correct 11 ms 7248 KB Output is correct
17 Correct 79 ms 21812 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 2 ms 4440 KB Output is correct
20 Incorrect 1 ms 4432 KB Output isn't correct
21 Halted 0 ms 0 KB -