Submission #3000210
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{
const size_t num = size_t(x.first) * 100000 + x.second;
return std::hash<size_t>()(num);
}
};
}
vint node;
//↓区間和を求めるSegmentTree
struct SegmentTreeSum {
private:
int n;
vector<int> node;
public:
// 元配列 v をセグメント木で表現する
SegmentTreeSum(const 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);
//クエリを処理する
vector<unordered_map<int,int> > pam(M+2);
pam.reserve(Q.size());
for(const 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[a][b] =S.getsum(b,M+1);
}
}
//答えを求める
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[b][b]-pam[a][b];
}
cout<<ans<<endl;
}
system("pause");
return 0;
}
Submission Info
Submission Time
2018-08-13 03:10:10+0900
Task
E - Snuke Line
User
kurenaif
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
4452 Byte
Status
TLE
Exec Time
2114 ms
Memory
162584 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:158:17: warning: ignoring return value of ‘int system(const char*)’, declared with attribute warn_unused_result [-Wunused-result]
system("pause");
^
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
AC
2 ms
504 KB
00_example_02.txt
AC
2 ms
504 KB
01.txt
AC
2 ms
504 KB
02.txt
AC
3 ms
632 KB
03.txt
AC
3 ms
632 KB
04.txt
AC
2 ms
504 KB
05.txt
AC
8 ms
1280 KB
06.txt
AC
8 ms
1400 KB
07.txt
AC
2 ms
504 KB
08.txt
AC
5 ms
888 KB
09.txt
AC
2 ms
512 KB
10.txt
AC
2 ms
628 KB
11.txt
AC
1032 ms
73664 KB
12.txt
TLE
2112 ms
160424 KB
13.txt
AC
509 ms
27744 KB
14.txt
AC
375 ms
22232 KB
15.txt
AC
353 ms
22236 KB
16.txt
AC
906 ms
57388 KB
17.txt
TLE
2112 ms
156884 KB
18.txt
AC
327 ms
20212 KB
19.txt
TLE
2113 ms
160280 KB
20.txt
TLE
2113 ms
162456 KB
21.txt
TLE
2113 ms
162584 KB
22.txt
TLE
2113 ms
161560 KB
23.txt
TLE
2112 ms
161560 KB
24.txt
TLE
2113 ms
151192 KB
25.txt
AC
528 ms
35204 KB
26.txt
AC
353 ms
22964 KB
27.txt
TLE
2113 ms
152344 KB
28.txt
AC
537 ms
33028 KB
29.txt
TLE
2112 ms
134808 KB
30.txt
AC
526 ms
34812 KB
31.txt
TLE
2110 ms
112152 KB
32.txt
AC
543 ms
33148 KB
33.txt
AC
360 ms
22972 KB
34.txt
TLE
2114 ms
160792 KB
35.txt
TLE
2113 ms
162328 KB
36.txt
AC
2 ms
504 KB
37.txt
TLE
2111 ms
143512 KB