ICPC Singapore 2015

a.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) x.begin(),x.end()
#define pcnt __builtin_popcountll
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;
typedef pair<ll,ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 205, INF = 1001001001;
const int MT = 20000000;
// const int MT = 15;

const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const string dv = "^<v>";

int n;
string s[MX], t;
map<char,int> dvx;

struct kmp {
  vi a;
  kmp(vector<P>& p):a(sz(p)+1,-1) {
    for (int i = 0, j = -1; i < sz(p); a[++i]=++j) {
      while (j>=0&&p[i]!=p[j]) j = a[j];
    }
  }
};

int main() {
  rep(i,4) dvx[dv[i]] = i;
  n = in();
  cin >> t;
  int m = sz(t);
  rep(i,n) cin >> s[i];
  int x = 0, y = 0;
  rep(i,n)rep(j,n) if (s[i][j] == 'R') x = i, y = j;
  int z = 0, ans = 1, tm = 0;
  vector<P> p;
  // map<Q,int> mp;
  P pre;
  rep(ti,MT) {
    // Q nq = Q(P(x,y),z);
    // if (mp.count(nq)) {
    //   ans = tm-mp[nq];
    //   break;
    // }
    // mp[nq] = tm;
    int v = dvx[t[z]];
    int ni = x+di[v];
    int nj = y+dj[v];
    if (ni>=0 && nj>=0 && ni<n && nj<n) {
      if (s[ni][nj] != '#') {
        x = ni; y = nj;
      }
    }
    z = (z+1)%m;
    ++tm;
    if (tm > MT/2 && pre != P(x,y)) p.pb(P(x,y));
    pre = P(x,y);
    // printf("%d %d %d %d\n", x, y, z, v);
  }
  kmp d(p);
  ans = sz(p)-d.a.back();
  // for (auto np : p) printf("%d %d\n", np.fi, np.se);
  // for (int e : d.a) printf("%d ", e); puts("");
  cout << ans << endl;
  return 0;
}

c.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 500005, INF = 1001001001;

struct uf {
  vi d;
  uf(){}
  uf(int mx):d(mx,-1){}
  int root(int x) {
    if (d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  void unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y]; d[y] = x;
  }
};


int main() {
  df(n);
  uf t(MX);
  int ans = 0;
  rep(i,n) {
    df(m);
    vi a(m);
    rep(j,m) a[j] = in();
    bool ok = true;
    map<int,int> mp;
    rep(j,m) {
      mp[t.root(a[j])]++;
    }
    for (auto p : mp) {
      if (-t.d[p.fi] != p.se) ok = false;
    }
    if (ok) {
      ans++;
      rep(j,m-1) t.unite(a[j],a[j+1]);
    }
  }
  printf("%d\n", ans);
  return 0;
}

d.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) x.begin(),x.end()
#define pcnt __builtin_popcountll
#define maxs(a,b) a = max(a,b)
#define mins(a,b) a = min(a,b)
#define double long double
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,int> DP;
typedef pair<P,int> Q;
typedef pair<ll,ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 100005, INF = 1001001001;
const double eps = 1e-10;

const int mod = 1000000007;
struct mint;
mint ex(mint a, ll t);
struct mint {
  ll x;
  mint(ll x=0):x(x%mod) {}
  void operator+=(mint a) { (x+=a.x)%=mod;}
  void operator-=(mint a) { (x+=mod-a.x)%=mod;}
  void operator*=(mint a) { (x*=a.x)%=mod;}
  void operator/=(mint a) { (x+=ex(a,mod-2).x)%=mod;}
  mint operator+(mint a) { return mint(x+a.x);}
  mint operator-(mint a) { return mint(x-a.x+mod);}
  mint operator*(mint a) { return mint(x*a.x);}
  mint operator/(mint a) { return mint(x*ex(a,mod-2).x);}
};
typedef vector<mint> vm;
mint ex(mint a, ll t) {
  if (!t) return 1;
  mint res = ex(a,t/2);
  res *= res;
  return (t&1)?res*a:res;
}

int c[100];
vector<DP> ds[2];

void enu(int g, vp& p) {
  vector<DP>& d = ds[g];
  int cnt = 1;
  rep(i,sz(p)) cnt *= (p[i].fi+1);
  d.reserve(cnt);
  d.pb(DP(0,1));
  rep(i,sz(p)) {
    int x = p[i].se, n = p[i].fi;
    double l = log((double)x);
    for (int j = sz(d)-1; j >= 0; --j) {
      double nx = d[j].fi;
      ll ny = d[j].se;
      rep(k,n) {
        nx += l;
        ny = ny*x%mod;
        d.pb(DP(nx,ny));
      }
    }
  }
}

int main() {
  string s;
  cin >> s;
  int n = sz(s)/2;
  rep(i,n) {
    c[atoi(s.substr(i*2,2).c_str())]++;
  }
  vp p;
  rep(i,100) if (c[i]) p.pb(P(c[i],i));
  sort(rng(p));
  reverse(rng(p));
  vi g(sz(p));
  ll s0 = 1, s1 = 1;
  rep(i,sz(p)) {
    if (s0 <= s1) {
      g[i] = 0;
      s0 *= (p[i].fi+1);
    } else {
      g[i] = 1;
      s1 *= (p[i].fi+1);
    }
  }
  rep(ti,2) {
    vp np;
    rep(i,sz(p)) if (g[i] == ti) np.pb(p[i]);
    enu(ti,np);
  }
  double sum = 0;
  rep(i,sz(p)) sum += log((double)p[i].se)*p[i].fi;
  sum /= 2;
  rep(i,2) sort(rng(ds[i]));
  int ni = sz(ds[1])-1;
  DP ans(0,1);
  rep(i,sz(ds[0])) {
    while (ni >= 0 && ds[0][i].fi+ds[1][ni].fi-eps > sum) ni--;
    if (ni < 0) break;
    maxs(ans, DP(ds[0][i].fi+ds[1][ni].fi, (ll)ds[0][i].se*ds[1][ni].se%mod));
  }
  mint as = ans.se;
  mint ss = 1;
  rep(i,sz(p)) ss *= ex(p[i].se,p[i].fi);
  as += ss/as;
  cout << as.x << endl;
  return 0;
}

e.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 100005, INF = 1001001001;

int a[MX];

int main() {
  df(n); df(p);
  rep(i,n) a[i] = in();
  swap(a[0],a[p]);
  sort(a+1,a+n);
  int cnt = 0, sum = 0, now = 0;
  rep(i,n) {
    now += a[i];
    if (now > 300) break;
    cnt++;
    sum += now;
  }
  printf("%d %d\n", cnt, sum);
  return 0;
}

f.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 100005, INF = 1001001001;

P p[MX];

int main() {
  df(n);
  rep(i,n) p[i].se = in(), p[i].fi = in();
  sort(p,p+n);
  int ans = 0, pre = -INF;
  rep(i,n) {
    if (pre < p[i].se) {
      pre = p[i].fi;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

g.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) x.begin(),x.end()
#define pcnt __builtin_popcountll
#define maxs(a,b) a = max(a,b)
#define mins(a,b) a = min(a,b)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;
typedef pair<ll,ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 3005, INF = 1001001001;

struct seg {
  vi d; int x2;
  seg(){}
  seg(int mx) {
    x2 = 1; while(x2 < mx) x2 <<= 1;
    d = vi(x2<<1, -INF);
  }
  void add(int i, int x) {
    for (i+=x2; i; i>>=1) d[i] = max(d[i],x);
  }
  int get(int a, int b, int i=1, int l=0, int r=-1) {
    if (r == -1) r = x2;
    if (a <= l && r <= b) return d[i];
    int c = (l+r)>>1;
    int res = -INF;
    if (a < c) maxs(res,get(a,b,i<<1,l,c));
    if (c < b) maxs(res,get(a,b,i<<1|1,c,r));
    return res;
  }
};

int a[MX];
ll s[MX];
inline ll sum(int l, int r) { return s[r+1]-s[l];}

int main() {
  df(n);
  rep(i,n) a[i] = in();
  rep(i,n) s[i+1] = s[i]+a[i];
  vector<seg> t(n+5,seg(n+5));
  int ans = 1;
  rep(i,n) {
    rep(j,i) {
      ll ns = sum(j+1,i);
      int p = lower_bound(s,s+n,s[j+1]-ns)-s;
      int now = -INF;
      p = max(0,p-1);
      if (p < j) now = t[j].get(p,j)+1;
      if (s[j+1] <= ns) maxs(now,2);
      t[i].add(j,now);
      // cout<<i<<" "<<j<<" "<<p<<" "<<now<<endl;
      maxs(ans,now);
    }
  }
  printf("%d\n", ans);
  return 0;
}

h.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) x.begin(),x.end()
#define pcnt __builtin_popcountll
#define maxs(a,b) a = max(a,b)
#define mins(a,b) a = min(a,b)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;
typedef pair<ll,ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 100000, INF = 1001001001;

vp p;
vi x, y;

int gcd(int a, int b) { return b?gcd(b,a%b):a;}
void add(int dx, int dy) {
  x.pb(x.back()+dx);
  y.pb(y.back()+dy);
}

int main() {
  df(n);
  p.pb(P(0,1));
  [&] {
    rep(i,MX) {
      vp np;
      rep(j,i) if (j) {
        int a = j, b = i-j;
        if (!a || !b) continue;
        if (gcd(a,b) != 1) continue;
        np.pb(P(a,b));
      }
      random_shuffle(rng(np));
      rep(j,sz(np)) {
        p.pb(np[j]);
        if (sz(p) == MX) return;
      }
    }
  }();
  // for (P a : p) cout<<a.fi<<" "<<a.se<<endl;
  sort(rng(p),[](P a, P b){return (ll)a.fi*b.se<(ll)b.fi*a.se;});
  x = y = vi(1,0);
  for (P a : p) add(a.fi,a.se);
  for (P a : p) add(a.se,-a.fi);
  for (P a : p) add(-a.fi,-a.se);
  for (P a : p) add(-a.se,a.fi);

  int l = 0;
  rep(i,sz(x)) mins(l,x[i]);
  rep(i,sz(x)) x[i] -= l;
  l = 0;
  rep(i,sz(y)) mins(l,y[i]);
  rep(i,sz(y)) y[i] -= l;
  rep(i,n) {
    printf("%d %d\n", x[i], y[i]);
  }
  return 0;
}

i.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 100005, INF = 1001001001;

const int mod = 1000000007;
struct mint;
mint ex(mint a, ll t);
struct mint {
  ll x;
  mint(ll x=0):x(x%mod) {}
  void operator+=(mint a) { (x+=a.x)%=mod;}
  void operator-=(mint a) { (x+=mod-a.x)%=mod;}
  void operator*=(mint a) { (x*=a.x)%=mod;}
  void operator/=(mint a) { (x+=ex(a,mod-2).x)%=mod;}
  mint operator+(mint a) { return mint(x+a.x);}
  mint operator-(mint a) { return mint(x-a.x+mod);}
  mint operator*(mint a) { return mint(x*a.x);}
  mint operator/(mint a) { return mint(x*ex(a,mod-2).x);}
};
typedef vector<mint> vm;
mint ex(mint a, ll t) {
  if (!t) return 1;
  mint res = ex(a,t/2);
  res *= res;
  return (t&1)?res*a:res;
}
struct comb {
  vm f, g;
  comb(int mx):f(mx+1),g(mx+1) {
    f[0] = 1;
    rep(i,mx) f[i+1] = f[i]*(i+1);
    g[mx] = ex(f[mx], mod-2);
    for (int i = mx; i > 0; --i) g[i-1] = g[i]*i;
  }
  mint c(int a, int b) {
    // cout << a << " " << b << endl;
    if (a < b) return 0;
    return f[a]*g[b]*g[a-b];
  }
};


int main() {
  vi as;
  rep(i,3) as.pb(in());
  sort(rng(as));
  int a = as[0];
  int b = as[1];
  int d = as[2];
  comb c(a+b+d+5);
  mint ans = 0;
  rep(i,a)rep(j,2)rep(k,2) {
    int na = a-i;
    int nb = na-1+j+k;
    if (nb > b || nb < 1) continue;
    if (a < (1-j)+(1-k)) continue;
    int bi = b-nb;
    int ci = i+bi;
    if (ci > d) continue;
    // cout<<j<<" "<<k<<" "<<na<<" "<<nb<<endl;
    // cout<<ci<<endl;
    mint now = 1;
    now *= c.c(a-1,na-1);
    now *= c.c(b-1,nb-1);
    int rc = d-ci, tt = a+b-ci;
    if (tt+1 < rc) continue;
    now *= c.c(tt+1,rc);
    ans += now;
  }
  printf("%d\n", ans);
  return 0;
}

j.cpp

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) x.begin(),x.end()
#define pcnt __builtin_popcountll
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
inline int in() { int x; scanf("%d",&x); return x;}

const int MX = 300005, INF = 1001001001;

struct bit {
  vvl d; int x2;
  bit(){}
  bit(int mx) {
    x2 = 1;
    while (x2 < mx) x2 <<= 1;
    d = vvl(2,vl(x2+1));
  }
  void add(int i, int x) {
    ++i;
    int xi = x/50;
    ll xj = 1ll<<(x%50);
    for (;i<=x2; i+=i&-i) {
      d[xi][i] ^= xj;
    }
  }
  LP sum(int i) {
    ++i;
    LP res(0,0);
    for (;i; i-=i&-i) {
      res.fi ^= d[0][i];
      res.se ^= d[1][i];
    }
    return res;
  }
};

vi to[MX];
int c[MX];
int vk[MX], k, vs[MX], vt[MX];

void dfs(int v) {
  vs[v] = k;
  vk[k++] = v;
  for (int u : to[v]) {
    dfs(u);
  }
  vt[v] = k;
}

int main() {
  df(n); df(q);
  rep(i,n) c[i] = in()-1;
  rep(i,n-1) {
    df(p);
    to[p-1].pb(i+1);
  }
  dfs(0);
  bit t(n+5);
  rep(i,n) t.add(vs[i],c[i]);
  rep(qi,q) {
    int tp, v;
    scanf("%d%d",&tp,&v);
    --v;
    if (tp) {
      --tp;
      t.add(vs[v],c[v]);
      t.add(vs[v],tp);
      c[v] = tp;
    } else {
      LP x = t.sum(vt[v]-1);
      LP y = t.sum(vs[v]-1);
      int ans = pcnt(x.fi^y.fi) + pcnt(x.se^y.se);
      printf("%d\n", ans);
    }
  }
  return 0;
}