oj.uz

답안 #447035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447035 2021-07-24T09:26:47 Z Jasiekstrz Vepar (COCI21_vepar) C++17
70 / 70
 963 ms 10200 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 947 ms 10148 KB Output is correct
2 Correct 947 ms 10084 KB Output is correct
3 Correct 959 ms 10088 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 943 ms 10172 KB Output is correct
2 Correct 939 ms 10160 KB Output is correct
3 Correct 946 ms 10088 KB Output is correct
4 Correct 949 ms 10152 KB Output is correct
5 Correct 957 ms 10092 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 947 ms 10052 KB Output is correct
2 Correct 952 ms 10080 KB Output is correct
3 Correct 962 ms 10084 KB Output is correct
4 Correct 947 ms 10088 KB Output is correct
5 Correct 938 ms 10084 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 952 ms 10088 KB Output is correct
2 Correct 951 ms 10088 KB Output is correct
3 Correct 946 ms 10084 KB Output is correct
4 Correct 952 ms 10180 KB Output is correct
5 Correct 956 ms 10088 KB Output is correct
6 Correct 910 ms 10088 KB Output is correct
7 Correct 949 ms 10084 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 944 ms 10092 KB Output is correct
2 Correct 953 ms 10148 KB Output is correct
3 Correct 954 ms 10080 KB Output is correct
4 Correct 937 ms 10144 KB Output is correct
5 Correct 946 ms 10088 KB Output is correct
6 Correct 941 ms 10088 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 947 ms 10088 KB Output is correct
2 Correct 947 ms 10124 KB Output is correct
3 Correct 948 ms 10084 KB Output is correct
4 Correct 954 ms 10052 KB Output is correct
5 Correct 944 ms 10096 KB Output is correct
6 Correct 930 ms 10088 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 939 ms 10180 KB Output is correct
2 Correct 933 ms 10084 KB Output is correct
3 Correct 939 ms 10088 KB Output is correct
4 Correct 940 ms 10184 KB Output is correct
5 Correct 963 ms 10200 KB Output is correct
6 Correct 924 ms 10148 KB Output is correct
7 Correct 935 ms 10196 KB Output is correct