제출 #373811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373811		Nimbostratus	Vepar (COCI21_vepar)	C++17	30 / 70	1604 ms	188520 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10