AtCoder Regular Contest 068

Submission #4024901

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(2e6)+10;
int n,m,lazy[maxn],sz[maxn],ans,cnt;
ll tr[maxn];
struct node { int l,r; };
vector<node> g[maxn/4];
void pushdown(int root) {
	if (!lazy[root]) return;
	tr[root*2]+=(ll)lazy[root]*sz[root*2];
	tr[root*2+1]+=(ll)lazy[root]*sz[root*2+1];
	lazy[root*2]+=lazy[root];
	lazy[root*2+1]+=lazy[root]; lazy[root]=0;
}
void build(int l,int r,int root) {
	sz[root]=r-l+1; if (l==r) return;
	int mid=(l+r)/2; build(l,mid,root*2); build(mid+1,r,root*2+1);
}
void add(int L,int R,int l,int r,int root) {
	if (L<=l&&r<=R) {
		tr[root]+=sz[root]; lazy[root]++; return;
	} pushdown(root);
	int mid=(l+r)/2;
	if (L<=mid) add(L,R,l,mid,root*2);
	if (mid<R) add(L,R,mid+1,r,root*2+1);
	tr[root]=tr[root*2]+tr[root*2+1];
}
int query(int x,int l,int r,int root) {
	if (l==r) return tr[root];
	pushdown(root);
	int mid=(l+r)/2;
	if (x<=mid) return query(x,l,mid,root*2);
	return query(x,mid+1,r,root*2+1);
}
int main() {
	//freopen("1.txt","r",stdin);
	read(m); read(n);
	int x,y;
	for (int i=1;i<=m;i++) {
		read(x); read(y);
		g[y-x+1].push_back((node){x,y});
	} build(1,n,1);
	for (int i=1;i<=n;i++) {
		for (int j=0;j<g[i].size();j++)
			add(g[i][j].l,g[i][j].r,1,n,1),m--;
		ans=m;
		for (int j=i;j<=n;j+=i)
			ans+=query(j,1,n,1);
		printf("%d\n",ans);
	}
	return 0;
}

Submission

Task問題 E - Snuke Line
User nameユーザ名 wygz
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 1605 Byte
File nameファイル名
Exec time実行時間 280 ms
Memory usageメモリ使用量 23680 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt
All 700 / 700 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 6 ms 16640 KB
00_example_02.txt AC 6 ms 16640 KB
01.txt AC 6 ms 16640 KB
02.txt AC 6 ms 16640 KB
03.txt AC 6 ms 16640 KB
04.txt AC 6 ms 16640 KB
05.txt AC 7 ms 16640 KB
06.txt AC 7 ms 16640 KB
07.txt AC 6 ms 16768 KB
08.txt AC 7 ms 16640 KB
09.txt AC 6 ms 16640 KB
10.txt AC 6 ms 16640 KB
11.txt AC 166 ms 22784 KB
12.txt AC 273 ms 23680 KB
13.txt AC 109 ms 20224 KB
14.txt AC 85 ms 20096 KB
15.txt AC 85 ms 19968 KB
16.txt AC 147 ms 20480 KB
17.txt AC 280 ms 23680 KB
18.txt AC 75 ms 20220 KB
19.txt AC 275 ms 23680 KB
20.txt AC 279 ms 23680 KB
21.txt AC 273 ms 23680 KB
22.txt AC 280 ms 23680 KB
23.txt AC 276 ms 23680 KB
24.txt AC 218 ms 21884 KB
25.txt AC 93 ms 19704 KB
26.txt AC 79 ms 19704 KB
27.txt AC 241 ms 22528 KB
28.txt AC 109 ms 20088 KB
29.txt AC 256 ms 22784 KB
30.txt AC 114 ms 20084 KB
31.txt AC 251 ms 22528 KB
32.txt AC 123 ms 19968 KB
33.txt AC 103 ms 20096 KB
34.txt AC 236 ms 22400 KB
35.txt AC 238 ms 22400 KB
36.txt AC 6 ms 16640 KB
37.txt AC 118 ms 18816 KB