Submission #3000198


Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=300050;
//ここまでテンプレ
//↓Binary Indexed Tree
struct BIT{
private:
	int n;
	vector<int> node;
public:
	//N要素のBITを作り、すべて0で初期化する
	//1-indexedであることに注意!!
	BIT(int N){
		node.resize(N+1,0);
		n=N;
	}
	//ノードiまでの和を計算する
	int sum(int i){
		if(!i)
			return 0;
		return node[i]+sum(i-(i&-i));
	}
	//ノードiにxを足す
	void add(int i,int x){
		if(i>n)
			return;
		node[i]+=x;
		add(i+(i&-i),x);
	}
};
//↑Binary Indexed Tree
int main(){
	int N,M;
	cin>>N>>M;
	//x=l,y=r
	//クエリ<x,0:区間,1:質問,y>
	multiset<tint> Q;
	//クエリに区間を入れる
	for(int i=0;i<N;i++){
		int l,r;
		cin>>l>>r;
		Q.insert(mt(l,0,r));
	}
	//クエリに質問を入れていく
	for(int i=1;i<=M;i++){
		for(int j=i;j<=M;j+=i){
			int a=j-i,b=j;
			//すでに入れてたら入れない
			if(Q.find(mt(b,1,b))==Q.end())
				Q.insert(mt(b,1,b));
			if(Q.find(mt(a,1,b))==Q.end())
				Q.insert(mt(a,1,b));
		}
	}
	//BIT
	BIT B(M+2);
	//クエリを処理する
	map<pint,int> pam;
	for(tint T:Q){
		int a,b,c;
		tie(a,c,b)=T;
		//区間クエリなら、区間を追加する
		if(c==0){
			//S.update(b,S.getsum(b,b+1)+1);
			B.add(b+1,1);
		}
		//質問クエリなら、質問に答える
		else{
			//pam[mp(a,b)]=S.getsum(b,M+1);
			pam[mp(a,b)]=B.sum(M+1)-B.sum(b);
		}
	}
	/*
	for(pair<pint,int> P:pam)
		cout<<P.first.first<<" "<<P.first.second<<" "<<P.second<<endl;
	*/
	//答えを求める
	for(int i=1;i<=M;i++){
		int ans=0;
		for(int j=i;j<=M;j+=i){
			int a=j-i,b=j;
			ans+=pam[mp(b,b)]-pam[mp(a,b)];
		}
		cout<<ans<<endl;
	}
	return 0;
}

Submission Info

Submission Time
Task E - Snuke Line
User takeo1116
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2680 Byte
Status TLE
Exec Time 2114 ms
Memory 175872 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 25
TLE × 14
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
01.txt AC 1 ms 256 KB
02.txt AC 2 ms 384 KB
03.txt AC 2 ms 384 KB
04.txt AC 1 ms 256 KB
05.txt AC 8 ms 1152 KB
06.txt AC 8 ms 1152 KB
07.txt AC 1 ms 256 KB
08.txt AC 4 ms 640 KB
09.txt AC 2 ms 256 KB
10.txt AC 2 ms 384 KB
11.txt AC 1390 ms 79360 KB
12.txt TLE 2114 ms 172544 KB
13.txt AC 412 ms 28416 KB
14.txt AC 331 ms 22272 KB
15.txt AC 346 ms 22272 KB
16.txt AC 1000 ms 61568 KB
17.txt TLE 2113 ms 172032 KB
18.txt AC 298 ms 20096 KB
19.txt TLE 2114 ms 175872 KB
20.txt TLE 2114 ms 175232 KB
21.txt TLE 2114 ms 171520 KB
22.txt TLE 2113 ms 163456 KB
23.txt TLE 2113 ms 175360 KB
24.txt TLE 2113 ms 167040 KB
25.txt AC 518 ms 34304 KB
26.txt AC 327 ms 23168 KB
27.txt TLE 2113 ms 168576 KB
28.txt AC 505 ms 34304 KB
29.txt TLE 2112 ms 150656 KB
30.txt AC 500 ms 34304 KB
31.txt TLE 2111 ms 129536 KB
32.txt AC 526 ms 34304 KB
33.txt AC 341 ms 23168 KB
34.txt TLE 2114 ms 173696 KB
35.txt TLE 2114 ms 170752 KB
36.txt AC 1 ms 256 KB
37.txt TLE 2112 ms 145408 KB