이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 bs binary_search
#define int int
using pii = pair<int,int>;
using ll = long long;
const int maxn = 1e7+5;
const int maxsq = 1e3+5;
const int inf = 2e9;
const int mod = 1e9+7;
int t,a,b,c,d;
short pre[maxn][45];
short val[maxn][45];
short cnt[maxn];
pair<pii,pii> q[15];
vector<int> arr;
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);
cin >> t;
for(int i=1;i<=t;i++) {
int idx = arr.size();
arr.resize(arr.size()+4);
cin >> arr[idx] >> arr[idx+1] >> arr[idx+2] >> arr[idx+3];
q[i] = {{arr[idx],arr[idx+1]},{arr[idx+2],arr[idx+3]}};
}
arr.pb(0);
sort(all(arr));
arr.resize(unique(all(arr))-arr.begin());
int k = arr.back();
int asz = arr.size()-1;
//for(int i=1;i<=asz;i++) cout << arr[i] << " ";
//cout << endl;
for(int i=2;i<=k;i++) {
int pos = lb(all(arr),i)-arr.begin();
bool val_ok = pos <= asz && arr[pos] == i;
int tmp = i;
for(int j=2;1ll*j*j<=tmp;j++)
while(tmp > 1 && tmp % j == 0) {
tmp /= j;
pre[j][pos]++;
val[j][pos] += val_ok;
}
if(tmp > 1) {
pre[tmp][pos]++;
val[tmp][pos] += val_ok;
}
}
for(int i=1;i<=k;i++)
for(int j=1;j<=asz;j++)
pre[i][j] += pre[i][j-1];
/*for(int i=1;i<=10;i++) {
cout << i << " : " << endl;
for(int j=1;j<=asz;j++) {
cout << pre[i][j] << " ";
}
cout << endl;
}
cout << endl << endl;
for(int i=1;i<=10;i++) {
cout << i << " : " << endl;
for(int j=1;j<=asz;j++) {
cout << val[i][j] << " ";
}
cout << endl;
}*/
while(t--) {
cout << "DA" << endl;
}
//for(int i=1;i<=t;i++) {
// int a,b,c,d;
// tie(a,b) = q[i].fi;
// tie(c,d) = q[i].se;
// int z = max(b,d);
// int loc_a = lb(all(arr),a)-arr.begin();
// int loc_b = lb(all(arr),b)-arr.begin();
// int loc_c = lb(all(arr),c)-arr.begin();
// int loc_d = lb(all(arr),d)-arr.begin();
// bool f = true;
// //cout << pre[2][loc_a] << " " << pre[2][loc_b] << " " << pre[2][loc_c] << " " << pre[2][loc_d] << endl;
// for(int j=2;j<=z;j++) {
// int r1 = pre[j][loc_b]-pre[j][loc_a]+val[j][loc_a];
// int r2 = pre[j][loc_d]-pre[j][loc_c]+val[j][loc_c];
// if(r1 > r2) {
// //cout << i << " " << j << " " << r1 << " " << r2 << endl;
// f = false;
// break;
// }
// }
// cout << (f ? "DA" : "NE") << endl;
//}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |