oj.uz

Submission #373811

# Submission time Handle Problem Language Result Execution time Memory
373811 2021-03-05T20:06:04 Z Nimbostratus Vepar (COCI21_vepar) C++17
30 / 70
 1500 ms 188520 KB 
#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 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;

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;
	}*/
	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;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1597 ms 186476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1553 ms 181732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1604 ms 188520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1561 ms 183916 KB Time limit exceeded
2 Halted 0 ms 0 KB -