제출 #447035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447035		Jasiekstrz	Vepar (COCI21_vepar)	C++17	70 / 70	963 ms	10200 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e7;
//const int N=15;
vector<tuple<int,int,int,int>> que;
bool ans[10];
bool comp[N+10];
int s[N+10];
vector<tuple<int,int,int>> srt;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		que.emplace_back(a,b,c,d);
		srt.emplace_back(a-1,i-1,1);
		srt.emplace_back(b,i-1,-1);
		srt.emplace_back(c-1,i-1,-1);
		srt.emplace_back(d,i-1,1);
	}
	sort(srt.begin(),srt.end());
	for(int i=2;i<=N;i++)
	{
		if(comp[i])
			continue;
		int pref=0;
		int it=0;
		for(int j=i;j<=N;j+=i)
		{
			while(it<4*q)
			{
				auto [a,b,c]=srt[it];
				if(a>=j)
					break;
				//cerr<<i<<" "<<a<<" "<<pref<<"\n";
				s[b]+=c*pref;
				it++;
			}
			comp[j]=true;
			for(int tmp=j;tmp%i==0;tmp/=i,pref++);
		}
		while(it<4*q)
		{
			auto [a,b,c]=srt[it];
			s[b]+=c*pref;
			it++;
		}
		for(int it=0;it<q;it++)
		{
			if(s[it]<0)
				ans[it]=true;
			s[it]=0;
		}
	}
	for(int i=0;i<q;i++)
		cout<<(ans[i] ? "NE":"DA")<<"\n";
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10