Submission #373786

#TimeUsernameProblemLanguageResultExecution timeMemory
373786NimbostratusVepar (COCI21_vepar)C++17
0 / 70
1587 ms7472 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ub upper_bound #define lb lower_bound #define clean(a,s) memset((a),0,sizeof((a)[0])*(s)) #define all(x) (x).begin() , (x).end() #define fi first #define se second #define int int using pii = pair<int,int>; using ll = long long; const int maxn = 1e7+5; const int inf = 2e9; const int mod = 1e9+7; int t,a,b,c,d; int cnt[maxn]; bitset<maxn> composite; int32_t main () { //freopen("in","r",stdin); freopen("out","w",stdout); ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); for(int i=2;i<maxn-2;i++) { if(composite[i]) continue; for(ll j=1ll*i*i;j<1ll*maxn-2;j+=i) composite[j] = true; } cin >> t; while(t--) { cin >> a >> b >> c >> d; for(int i=a;i<=b;i++) { if(!composite[i]) { cnt[i]++; continue; } int tmp = i; for(int j=2;1ll*j*j<=tmp;j++) while(tmp > 1 && tmp % j == 0) { tmp /= j; cnt[j]++; } if(tmp > 1) cnt[tmp]++; } for(int i=c;i<=d;i++) { if(!composite[i]) { cnt[i]--; continue; } int tmp = i; for(int j=2;1ll*j*j<=tmp;j++) { while(tmp > 1 && tmp % j == 0) { tmp /= j; cnt[j]--; } } if(tmp > 1) cnt[tmp]--; } int z = max(c,d); bool f = true; for(int i=2;i<=z;i++) if(cnt[i] > 0) { f = false; break; } cout << (f ? "DA" : "NE") << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...