oj.uz

Submission #373812

# Submission time Handle Problem Language Result Execution time Memory
373812 2021-03-05T20:10:48 Z Nimbostratus Vepar (COCI21_vepar) C++17
0 / 70
 1500 ms 187116 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 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;
	//}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1593 ms 187116 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 1575 ms 185676 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 1580 ms 186848 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 1606 ms 186600 KB Time limit exceeded
2 Halted 0 ms 0 KB -