Submission #3000186
Source Code Expand
// author: https://arc068.contest.atcoder.jp/users/takeo1116, https://arc068.contest.atcoder.jp/users/kurenaif
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cassert>
#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;
//ここまでテンプレ
namespace std {
template <>
class hash<std::pair<int, int>> {
public:
size_t operator()(const std::pair<int, int>& x) const{
return hash<int>()(x.first) ^ hash<int>()(x.second);
}
};
}
vint node;
//↓区間和を求めるSegmentTree
struct SegmentTreeSum {
private:
int n;
vector<int> node;
public:
// 元配列 v をセグメント木で表現する
SegmentTreeSum(vector<int> v) {
// 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
// セグメント木全体で必要なノード数は 2n-1 個である
int sz = v.size();
n = 1; while(n < sz) n *= 2;
node.resize(2*n-1, 0);
// 最下段に値を入れたあとに、下の段から順番に値を入れる
// 値を入れるには、自分の子の 2 値を参照すれば良い
for(int i=0; i<sz; i++) node[i+n-1] = v[i];
for(int i=n-2; i>=0; i--) node[i] = (node[2*i+1] + node[2*i+2]);
}
void update(int x, int val) {
// 最下段のノードにアクセスする
x += (n - 1);
// 最下段のノードを更新したら、あとは親に上って更新していく
node[x] = val;
while(x > 0) {
x = (x - 1) / 2;
node[x] = (node[2*x+1] + node[2*x+2]);
}
}
int getsum(int a, int b, int k=0, int l=0, int r=-1) {
// 最初に呼び出されたときの対象区間は [0, n)
if(r < 0) r = n;
// 要求区間と対象区間が交わらない -> 適当に返す
if(r <= a || b <= l) return 0;
// 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
if(a <= l && r <= b) return node[k];
// 要求区間が対象区間の一部を被覆 -> 子について探索を行う
// 左側の子を vl ・ 右側の子を vr としている
// 新しい対象区間は、現在の対象区間を半分に割ったもの
int vl = getsum(a, b, 2*k+1, l, (l+r)/2);
int vr = getsum(a, b, 2*k+2, (l+r)/2, r);
return (vl + vr);
}
};
//↑区間和を求めるSegmentTree
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));
}
}
//セグ木
for(int i=0;i<=M+1;i++)
node.pb(0);
SegmentTreeSum S(node);
//クエリを処理する
unordered_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);
//質問クエリなら、質問に答える
else{
pam[mp(a,b)]=S.getsum(b,M+1);
}
}
assert(false);
//答えを求める
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 |
kurenaif |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4373 Byte |
Status |
RE |
Exec Time |
2110 ms |
Memory |
110124 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 700 |
Status |
|
|
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 |
RE |
96 ms |
256 KB |
00_example_02.txt |
RE |
96 ms |
256 KB |
01.txt |
RE |
97 ms |
256 KB |
02.txt |
RE |
98 ms |
384 KB |
03.txt |
RE |
98 ms |
384 KB |
04.txt |
RE |
96 ms |
256 KB |
05.txt |
RE |
107 ms |
1152 KB |
06.txt |
RE |
107 ms |
1280 KB |
07.txt |
RE |
96 ms |
256 KB |
08.txt |
RE |
100 ms |
640 KB |
09.txt |
RE |
97 ms |
256 KB |
10.txt |
RE |
97 ms |
384 KB |
11.txt |
TLE |
2107 ms |
58628 KB |
12.txt |
TLE |
2110 ms |
109356 KB |
13.txt |
RE |
1179 ms |
28324 KB |
14.txt |
RE |
515 ms |
22144 KB |
15.txt |
RE |
510 ms |
22144 KB |
16.txt |
TLE |
2106 ms |
49444 KB |
17.txt |
TLE |
2110 ms |
106556 KB |
18.txt |
RE |
421 ms |
20096 KB |
19.txt |
TLE |
2110 ms |
109356 KB |
20.txt |
TLE |
2110 ms |
109612 KB |
21.txt |
TLE |
2110 ms |
109612 KB |
22.txt |
TLE |
2109 ms |
110124 KB |
23.txt |
TLE |
2110 ms |
109612 KB |
24.txt |
TLE |
2110 ms |
109484 KB |
25.txt |
TLE |
2105 ms |
33316 KB |
26.txt |
RE |
554 ms |
23296 KB |
27.txt |
TLE |
2110 ms |
109228 KB |
28.txt |
TLE |
2105 ms |
33316 KB |
29.txt |
TLE |
2110 ms |
108844 KB |
30.txt |
TLE |
2105 ms |
33316 KB |
31.txt |
TLE |
2110 ms |
108552 KB |
32.txt |
TLE |
2104 ms |
33956 KB |
33.txt |
RE |
565 ms |
23296 KB |
34.txt |
TLE |
2110 ms |
109612 KB |
35.txt |
TLE |
2110 ms |
109612 KB |
36.txt |
RE |
97 ms |
256 KB |
37.txt |
TLE |
2109 ms |
90668 KB |