제출 #382044

#제출 시각아이디문제언어결과실행 시간메모리
382044VimmerVepar (COCI21_vepar)C++14
30 / 70
1620 ms249744 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("Ofast") #pragma GCC optimize("-O3") #pragma GCC optimize("unroll-loops") #define N 100500 #define NN 10000005 #define PB push_back #define endl '\n' #define pri(x) cout << x << endl #define _ << " " << #define sz(x) int(x.size()) #define F first #define S second #define all(x) x.begin(), x.end() using namespace std; //using namespace __gnu_pbds; typedef long long ll; //typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ord_set; vector <int> vr[NN], pr; int mk[NN], id; bool mkr[NN]; int kol[NN]; int main() { ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("1.in", "r", stdin); for (int i = 2; i < NN; i++) { if (mkr[i]) continue; pr.PB(i); for (ll j = 1ll * i * i; j < NN; j += i) mkr[j] = 1; } int q; cin >> q; for (; q > 0; q--) { int a, b, c, d; cin >> a >> b >> c >> d; if (c <= a && b <= d) { pri("DA"); continue; } if (a < c && d < b) { pri("NE"); continue; } if (a <= c && c <= b && b <= d) { int l = c; c = b + 1; b = l - 1; } id++; for (int i = c; i <= d; i++) { if (sz(vr[i]) == 0) { int x = i; for (auto it : pr) { if (x < it) break; while (x % it == 0) { x /= it; vr[i].PB(it); } } } for (auto it : vr[i]) { if (mk[it] != id) { mk[it] = id; kol[it] = 0; } kol[it]++; } } bool gd = 1; for (int i = a; i <= b && gd; i++) { if (sz(vr[i]) == 0) { int x = i; for (auto it : pr) { if (x < it) break; while (x % it == 0) { x /= it; vr[i].PB(it); } } } for (auto it : vr[i]) { if (mk[it] != id) { gd = 0; break; } kol[it]--; if (kol[it] == -1) { gd = 0; break; } } } if (gd) { pri("DA"); } else { pri("NE"); } } }
#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...