Submission #3000214
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<vector<int>> pam(M+2, vector<int>(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:11:37+0900
Task
E - Snuke Line
User
kurenaif
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
4458 Byte
Status
TLE
Exec Time
2518 ms
Memory
2027384 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
500 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
760 KB
04.txt
AC
2 ms
504 KB
05.txt
AC
8 ms
4344 KB
06.txt
AC
9 ms
4472 KB
07.txt
AC
2 ms
504 KB
08.txt
AC
5 ms
1536 KB
09.txt
AC
2 ms
512 KB
10.txt
AC
2 ms
632 KB
11.txt
TLE
2518 ms
-986240 KB
12.txt
TLE
2228 ms
1997560 KB
13.txt
AC
582 ms
241732 KB
14.txt
AC
400 ms
53624 KB
15.txt
AC
404 ms
52728 KB
16.txt
TLE
2316 ms
-735616 KB
17.txt
TLE
2238 ms
-2030980 KB
18.txt
AC
360 ms
24052 KB
19.txt
TLE
2221 ms
1880952 KB
20.txt
TLE
2217 ms
1793912 KB
21.txt
TLE
2220 ms
1877240 KB
22.txt
TLE
2222 ms
1910520 KB
23.txt
TLE
2220 ms
1894904 KB
24.txt
TLE
2213 ms
1763192 KB
25.txt
MLE
749 ms
551808 KB
26.txt
AC
401 ms
70264 KB
27.txt
TLE
2214 ms
1780984 KB
28.txt
MLE
746 ms
551808 KB
29.txt
TLE
2201 ms
1558264 KB
30.txt
MLE
732 ms
551912 KB
31.txt
TLE
2177 ms
1167608 KB
32.txt
MLE
753 ms
551912 KB
33.txt
AC
411 ms
70264 KB
34.txt
TLE
2224 ms
1967352 KB
35.txt
TLE
2232 ms
2027384 KB
36.txt
AC
2 ms
500 KB
37.txt
TLE
2224 ms
1960184 KB