POJ 2886(セグメントツリー)
3302 ワード
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 511111
#define INF 1000000009
#define pl c<<1
#define pr (c<<1)|1
#define lson tree[c].l,tree[c].mid,c<<1
#define rson tree[c].mid+1,tree[c].r,(c<<1)|1
int n, k;
char name[maxn][15];
int num[maxn];
struct node {
int l, r, mid;
int sum;
}tree[maxn<<4];
int Max[maxn], f[maxn]; //i i
void pushup (int c) {
if (tree[c].l == tree[c].r )
return ;
tree[c].sum = tree[pl].sum + tree[pr].sum;
}
void build_tree (int l, int r, int c) {
tree[c].l = l, tree[c].r = r, tree[c].mid = (l+r)>>1;
if (l == r) {
tree[c].sum = 1;
return ;
}
build_tree (lson);
build_tree (rson);
pushup (c);
}
void update (int l, int r, int c, int k) { // k 0
if (l == r) {
tree[c].sum = 0;
return ;
}
if (tree[c].mid-l+1 >= k) {
update (lson, k);
}
else update (rson, k-(tree[c].mid-l+1));
pushup (c);
}
int get_sum (int l, int r, int c, int x, int y) { //x y
if (x > y) {
return 0;
}
if (l == x && r == y) {
return tree[c].sum;
}
else if (y > tree[c].mid) {
return get_sum (lson, x, tree[c].mid) + get_sum (rson, tree[c].mid+1, y);
}
else return get_sum (lson, x, y);
}
int query (int l, int r, int c, int gg) { // gg
if (l == r)
return l;
if (tree[pl].sum >= gg) {
return query (lson, gg);
}
else return query (rson, gg-tree[pl].sum);
}
void debug (int l, int r, int c) {
cout << l << " " << r << endl;
cout << tree[c].sum << endl;
if (l == r)
return ;
debug (lson);
debug (rson);
}
int main () {
//freopen ("in", "r", stdin);
memset (f, 0, sizeof f);
for (int i = 1; i <= 500000; i++) {
for (int j = i; j <= 500000; j+= i)
f[j]++;
}
Max[1] = 1;
for (int i = 2; i <= 500000; i++) {
Max[i] = (f[Max[i-1]] >= f[i] ? Max[i-1] : i);
}
while (scanf ("%d%d", &n, &k) == 2) {
for (int i = 1; i <= n; i++) {
scanf ("%s %d", name[i], &num[i]);
}
build_tree (1, n, 1);
for (int i = 1; i <= Max[n]-1; i++) {
update (1, n, 1, k); // k
if (num[k] > 0) {
int pre = get_sum (1, n, 1, 1, k-1);
k = (pre+num[k]) % tree[1].sum;
if (k == 0)
k = tree[1].sum;
k = query (1, n ,1, k);
}
else {
num[k]++;
num[k] = (-num[k]) % tree[1].sum;
int pre = get_sum (1, n, 1, 1, k-1);
if (pre > num[k]) {
k = pre-num[k];
}
else {
int gg = num[k]-pre;
k = tree[1].sum - gg;
}
k = query (1, n, 1, k);
}
}
printf ("%s %d
", name[k], f[Max[n]]);
}
return 0;
}