Submission #1359202
Source Code Expand
#include <iostream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <algorithm> #include <sstream> #include <cmath> #include <set> #include <iomanip> #include <deque> #include <limits> using namespace std; typedef long long ll; #define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--) #define FOREACH(i,Itr) for(auto (i)=(Itr).begin();(i)!=(Itr).end();(i)++) #define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end()) #define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end()) #define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val)) #define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val)) template <class T> struct FenwickTree { vector<T> node; FenwickTree (int n) : node(n,0) {} void add(int idx, T val) { for (int i = idx; i < node.size(); i |= i + 1) { node[i] += val; } } T sum(int idx) { T ret = 0; for (int i = idx - 1; i >= 0; i = (i & (i + 1)) - 1) { ret += node[i]; } return ret; } }; int N,M; vector< pair<int,int> > add; vector<int> l,r; FenwickTree<int> inst(100010); int main() { cin >> N >> M; l.resize(N); r.resize(N); REP(i,N) { int lt,rt; cin >> lt >> rt; l[i] = lt; r[i] = rt; add.push_back(make_pair(rt - lt + 1, i)); } sort(add.begin(),add.end()); int j = 0; for(int i=1; i<=M; i++) { while(j < add.size()) { if(add[j].first >= i) break; int idx = add[j].second; inst.add(l[idx],1); inst.add(r[idx]+1,-1); j++; } int ans = N - j; for(int k=i; k<=M; k+=i) ans += inst.sum(k+1); cout << ans << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke Line |
User | kosakkun |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1889 Byte |
Status | AC |
Exec Time | 396 ms |
Memory | 9200 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 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 | 1 ms | 640 KB |
00_example_02.txt | AC | 1 ms | 640 KB |
01.txt | AC | 1 ms | 640 KB |
02.txt | AC | 3 ms | 768 KB |
03.txt | AC | 2 ms | 640 KB |
04.txt | AC | 1 ms | 640 KB |
05.txt | AC | 3 ms | 640 KB |
06.txt | AC | 3 ms | 640 KB |
07.txt | AC | 1 ms | 640 KB |
08.txt | AC | 2 ms | 640 KB |
09.txt | AC | 2 ms | 640 KB |
10.txt | AC | 2 ms | 640 KB |
11.txt | AC | 282 ms | 8176 KB |
12.txt | AC | 388 ms | 7664 KB |
13.txt | AC | 209 ms | 8304 KB |
14.txt | AC | 203 ms | 7664 KB |
15.txt | AC | 201 ms | 8816 KB |
16.txt | AC | 263 ms | 7536 KB |
17.txt | AC | 379 ms | 8432 KB |
18.txt | AC | 197 ms | 9072 KB |
19.txt | AC | 387 ms | 7536 KB |
20.txt | AC | 392 ms | 7408 KB |
21.txt | AC | 390 ms | 7920 KB |
22.txt | AC | 389 ms | 8688 KB |
23.txt | AC | 390 ms | 8048 KB |
24.txt | AC | 381 ms | 8304 KB |
25.txt | AC | 230 ms | 8560 KB |
26.txt | AC | 202 ms | 9200 KB |
27.txt | AC | 391 ms | 7920 KB |
28.txt | AC | 236 ms | 8560 KB |
29.txt | AC | 396 ms | 7664 KB |
30.txt | AC | 251 ms | 8816 KB |
31.txt | AC | 385 ms | 7664 KB |
32.txt | AC | 240 ms | 8688 KB |
33.txt | AC | 209 ms | 8688 KB |
34.txt | AC | 382 ms | 8560 KB |
35.txt | AC | 389 ms | 8304 KB |
36.txt | AC | 2 ms | 640 KB |
37.txt | AC | 168 ms | 768 KB |