oj.uz

Submission #489675

# Submission time Handle Problem Language Result Execution time Memory
489675 2021-11-23T18:20:38 Z inksamurai Vepar (COCI21_vepar) C++17
70 / 70
 1020 ms 172096 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3oIUrY0 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<ll,ll>;
using vi=vector<ll>;

const ll _n=1e7+20;
ll a[_n+10],b[_n+10];
bool sv[_n+10];

int main(){
_3oIUrY0;
	for(ll i=2;i<=_n;i++){
		if(sv[i]) continue;
		for(ll j=2*i;j<=_n;j+=i){
			if(sv[j]==0) sv[j]=i;
		}
	}
	vi prms;
	for(ll i=2;i<=_n;i++){
		if(!sv[i]){
			prms.pb(i);
		}
	}
	auto f=[&](ll prm,ll n)->ll{
		if(prm>n) return 0;
		ll x=prm;
		vi rbts;
		while(x<=n){
			rbts.pb(x);
			x*=prm;
		}
		ll _sum=0,now=0;
		drep(i,sz(rbts)){
			x=rbts[i];
			now+=((n/x)-_sum)*(i+1);
			_sum+=((n/x)-_sum);
		}
		return now;
	};
	ll t;
	cin>>t;
	rep(cs,t){
		ll _a,_b,_c,_d;
		cin>>_a>>_b>>_c>>_d;
		for(auto prm : prms){
			b[prm]+=f(prm,_b);
			b[prm]-=f(prm,_a-1);
			a[prm]+=f(prm,_d);
			a[prm]-=f(prm,_c-1);
		}
		bool pok=1;
		for(auto prm : prms){
			if(b[prm]>a[prm]){
				pok=0;
			}
			a[prm]=b[prm]=0;
		}
		cout<<(pok?"DA":"NE")<<"\n";
	}
//	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 171972 KB Output is correct
2 Correct 499 ms 171972 KB Output is correct
3 Correct 516 ms 171940 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 171956 KB Output is correct
2 Correct 475 ms 172076 KB Output is correct
3 Correct 479 ms 171972 KB Output is correct
4 Correct 474 ms 171968 KB Output is correct
5 Correct 498 ms 171960 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 171944 KB Output is correct
2 Correct 486 ms 171968 KB Output is correct
3 Correct 477 ms 171976 KB Output is correct
4 Correct 474 ms 171960 KB Output is correct
5 Correct 495 ms 171856 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 171984 KB Output is correct
2 Correct 548 ms 171940 KB Output is correct
3 Correct 663 ms 171944 KB Output is correct
4 Correct 589 ms 171972 KB Output is correct
5 Correct 580 ms 171984 KB Output is correct
6 Correct 430 ms 172096 KB Output is correct
7 Correct 662 ms 171968 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 171976 KB Output is correct
2 Correct 529 ms 171988 KB Output is correct
3 Correct 520 ms 171944 KB Output is correct
4 Correct 533 ms 171856 KB Output is correct
5 Correct 542 ms 171972 KB Output is correct
6 Correct 718 ms 171968 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 171848 KB Output is correct
2 Correct 503 ms 171948 KB Output is correct
3 Correct 520 ms 171968 KB Output is correct
4 Correct 663 ms 171988 KB Output is correct
5 Correct 660 ms 171988 KB Output is correct
6 Correct 776 ms 172044 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 825 ms 171940 KB Output is correct
2 Correct 644 ms 171972 KB Output is correct
3 Correct 679 ms 171968 KB Output is correct
4 Correct 672 ms 171944 KB Output is correct
5 Correct 773 ms 171968 KB Output is correct
6 Correct 941 ms 171972 KB Output is correct
7 Correct 1020 ms 171896 KB Output is correct