Arithmetic Progression
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
int n, a[N];
#define ls o << 1
#define rs o << 1 | 1
LL min[N << 2], tag[N << 2];
int cnt[N << 2], gcd[N << 2];
void pushup(int o) {
min[o]=std::min(min[o*2],min[o*2+1]);
cnt[o]=0;
if(min[o]==min[o*2]){
cnt[o]+=cnt[o*2];
}
if(min[o]==min[o*2+1]){
cnt[o]+=cnt[o*2+1];
}
min[o] += tag[o];
if(gcd[o*2]==gcd[o*2+1]){
gcd[o]=gcd[o*2];
}else{
gcd[o]=-1;
}
}
void add(int o, int l, int r, int x, int y, int z) {
if (x <= l && r <= y) {
min[o] += z;
tag[o] += z;
return;
}
int m = l + r >> 1;
if (x <= m) add(ls, l, m, x, y, z);
if (y > m) add(rs, m + 1, r, x, y, z);
pushup(o);
}
int ask(int o, int l, int r, int x, int y, int z) {
if (y < l || r < x) return 0;
if (x <= l && r <= y) return min[o] + z == 0 ? cnt[o] : 0;
int m = l + r >> 1;
z += tag[o];
return ask(ls, l, m, x, y, z) + ask(rs, m + 1, r, x, y, z);
}
int s1[N], s2[N], t1, t2; // min, max
void update(int rt,int l,int r,int L,int R,int z){
if(gcd[rt]>0&&z%gcd[rt]==0){
min[rt]-=gcd[rt];
tag[rt]-=gcd[rt];
return;
}
int mid=(l+r)>>1;
if(l==r){
int t=gcd[rt];
gcd[rt]=std::gcd(gcd[rt],z);
min[rt]-=(gcd[rt]-t)*(R-l)+gcd[rt];
cnt[rt]=1;
return;
}
if(L<=mid)update(rt*2,l,mid,L,R,z);
if(R>mid)update(rt*2+1,mid+1,r,L,R,z);
pushup(rt);
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
std::cin >> n;
memset(min, 0, n + 1 << 5);
memset(tag, 0, n + 1 << 5);
memset(cnt, 0, n + 1 << 4);
memset(gcd, 0, n + 1 << 4);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
LL ans = n;
t1 = t2 = s1[1] = s2[1] = 1;
for (int i = 2; i <= n; i++) {
while (t1 && a[s1[t1]] > a[i]) {
add(1, 1, n, s1[t1 - 1] + 1, s1[t1], a[s1[t1]]);
t1--;
}
while (t2 && a[s2[t2]] < a[i]) {
add(1, 1, n, s2[t2 - 1] + 1, s2[t2], -a[s2[t2]]);
t2--;
}
add(1, 1, n, s1[t1] + 1, i, -a[i]);
add(1, 1, n, s2[t2] + 1, i, a[i]);
s1[++t1] = s2[++t2] = i;
update(1, 1, n, 1, i - 1, a[i] - a[i - 1]);
ans += ask(1, 1, n, 1, i - 1, 0);
}
std::cout << ans << "\n";
}
return 0;
}Cannon
#include<bits/stdc++.h>
using namespace std;
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () { cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}
#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e7 + 10;
const int maxm = 6e2 + 10;
const int mod = 1e9 + 9;
const int P = 131;
const int S = 5;
inline ll rd() {
ll f = 0; ll x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
if (f) x = -x;
return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
int n, m, s[maxn], s1[maxn], s2[maxn];
int f1[maxn], f2[maxn], qpow2[maxn], inv[maxn];
ll qpow(ll n, ll k, ll mod) {
ll ans = 1;
while(k) {
if(k & 1)
ans = ans * n % mod;
n = n * n % mod;
k >>= 1;
}
return ans;
}
void init(){
s[0] = 1;
s[1] = 1;
qpow2[0] = 1;
qpow2[1] = 2;
inv[0] = 1;
inv[1] = 1;
for(int i = 2; i <= maxn - 5; ++i) {
inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
}
for(ll i = 2; i <= maxn - 5; i++){
s[i] = (ll)s[i - 1] * i % mod;
qpow2[i] = (ll)qpow2[i - 1] * 2ll % mod;
inv[i] = (ll)inv[i - 1] * (ll)inv[i] % mod;
}
}
ll c(ll n, ll m){
if(n < m) return 0;
return (ll)s[n] * (ll)inv[m] % mod * (ll)inv[n - m] % mod;
}
void solve(){
n = rd(), m = rd();
n -= 2, m -= 2;
s1[n + m] = 1;
for(int i = n + m; i >= 1; i--) {
s1[i - 1] = ((2ll * s1[i] % mod - 1ll * c(n + m - i, n) % mod + mod)) % mod;
}
s2[n - 1] = 1;
for(int i = n - 1; i >= 1; i--) {
// s2[i - 1] = ((s2[i] % mod + 1ll * c(n + m - i, n - i) % mod + mod)) % mod;
s2[i - 1] = ((2ll * s2[i ] % mod + 1ll * c(n + m - i, n - i) % mod + mod)) % mod;
}
//cout<<"DD"<<s2[m+n]<<endl;
for(int i = n + m; i >= 0; i--) {
s1[i] = (s1[i] - s2[i] + mod) % mod;
}
ll ans1 = 0, ans2 = 0;
for(int i = 0; i <= n + m; i++) {
f1[i] = (ll)qpow2[i] * s[n + m] % mod * inv[n + m - i] % mod;
f2[i] = (ll)qpow2[i] * s[n] % mod * s[m] % mod * inv[n + m - i] % mod * s1[i] % mod;
}
for(int i = 0; i <= n + m; i++) {
ans1 ^= f1[i];
ans2 ^= f2[i];
}
printf("%lld %lld\n", ans1, ans2);
}
int main() {
int t = 1;
init();
while(t--)
solve();
return 0;
}Draw Grids
#include<iostream>
using namespace std;
int n,m;
int main(){
cin>>n>>m;
int ans=(n-1)*m+(m-1);
if(ans&1) puts("YES");
else puts("NO");
}Er Ba Game
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N =1e5+10,M =2*N;
int a[2020][2020];
int ver[M], edge[M],nxt[M], head[N], tot,val[N];
int root,n;
void add(int x, int y) {
ver[++tot]=y, nxt[tot]=head[x], head[x]=tot;
}
set<int>s;
void dfs(int x,int fa){
cout<<x<<" "<<fa<<endl;
s.insert(val[x]);
a[root][x]=s.size();
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa)continue;
s.insert(val[y]);
dfs(y,x);
s.erase(s.find(val[y]));
}
}
signed main() {
// freopen("1009.in","r",stdin);
int T;
cin>>T;
while(T--){
tot=0;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)head[i]=0;
for(int i=2;i<=n;i++){
int y;scanf("%d",&y);
add(i,y);add(y,i);
}
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(root=1;root<=n;root++){
dfs(root,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",a[i][j]);
}
cout<<endl;
}
}
return 0;
}Gas Station
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int N = 100010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], a[N],idx;
bool st[N];
int in[N],id[N],out[N];
struct node{
int d,p,id;
};
vector<node>ans[N];
int Res[N];
int cnt;
int sum[N],up[N],dn[N];
int p[N];
int c[N];
void add(int p, int x) {
for (; p <= cnt; p += p & -p) c[p] += x;
}
int ask(int p) {
int r = 0;
for (; p; p -= p & -p) r += c[p];
return r;
}
void pre(int x,int fa){
if(st[x])return;
in[x]=++cnt;
id[cnt]=x;
for(int i=h[x];~i;i=ne[i]){
int y=e[i];
if(y==fa)continue;
pre(y,x);
}
out[x]=cnt;
}
void get_dist(int u,int fa){
if(st[u])return;
for(int i=h[u];~i;i=ne[i]){
int y=e[i];
if(y == fa)continue;
sum[y]=sum[u]+a[y]-w[i];
up[y]=max((long long)0,up[u]+w[i]-a[y]);
dn[y]=max(dn[u],w[i]-sum[u]);
get_dist(y,u);
}
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int get_wc(int u, int fa, int tot, int& wc) // 求重心
{
if (st[u]) return 0;
int sum = 1, ms = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
int t = get_wc(j, u, tot, wc);
ms = max(ms, t);
sum += t;
}
ms = max(ms, tot - sum);
if (ms <= tot / 2) wc = u;
return sum;
}
int get_size(int u,int fa){
if(st[u])return 0;
int res=1;
for(int i=h[u];~i;i=ne[i]){
if(e[i]!=fa){
res+=get_size(e[i],u);
}
}
return res;
}
struct Qry {
long long d;
int l, r, p, id;
bool operator<(const Qry &rhs) const {
return d < rhs.d;
}
} s[N];
int tot;
void calc(int u){
// cout<<u<<endl;
if(st[u])return;
int res=0;
get_wc(u,-1,get_size(u,-1),u);
cnt=tot=0;
up[u] = dn[u] = 0;
sum[u] = a[u];
pre(u,0);
get_dist(u,-1);
st[u]=true;
for (auto [d, p, id] : ans[u]) {
if (p == u) continue;
int l = 0, r = 0;
if (in[p]) l = in[p], r = out[p];
s[++tot] = {d, l, r, 0, id};
}
for(int i=h[u];~i;i=ne[i]){
int y=e[i];
if(st[y])continue;
for (int i = in[y]; i <= out[y]; i++) {
int x = id[i];
for (auto [d, p, id] : ans[x]) {
if (d < up[x] || in[p] <= in[x] && out[x] <= out[p]) continue;
int l = 0, r = 0;
if(in[p] && !(in[y] <= in[p] && out[p] <= out[y])) l = in[p], r = out[p];
s[++tot] = {d + sum[x] - a[u], l, r, y, id};
}
}
}
std::sort(s + 1, s + 1 + tot);
for (int i = 1; i <= cnt; i++) p[i] = id[i];
std::sort(p + 1, p + 1 + cnt, [&](int i, int j) {
return dn[i] < dn[j];
});
for (int i = 1; i <= cnt; i++) c[i] = 0;
for (int i = 1, j = 1; i <= tot; i++) {
for (; j <= cnt && dn[p[j]] <= s[i].d; j++) {
add(in[p[j]], 1);
}
Res[s[i].id] += j - 1;
if (s[i].l) Res[s[i].id] -= ask(s[i].r) - ask(s[i].l - 1);
if (s[i].p) Res[s[i].id] -= ask(out[s[i].p]) - ask(in[s[i].p] - 1);
// std::cerr << "!! " << ans[s[i].id] << "\n";
}
for (int i = 1; i <= cnt; i++) {
in[id[i]] = out[id[i]] = 0;
}
for(int i=h[u];~i;i=ne[i])calc(e[i]);
}
signed main(){
scanf("%lld%lld",&n,&m);
memset(h,-1,sizeof h);
idx=0;
for(int i=0;i<n-1;i++){
int a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=m;i++){
int x,d,p;
scanf("%lld%lld%lld",&x,&d,&p);
ans[x].push_back((node){d,p,i});
}
calc(1);
for(int i=1;i<=m;i++){
printf("%lld\n",Res[i]);
}
return 0;
}Girlfriend
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
struct node{
double x,y,z;
}a,b,c,d;
struct circle{
double r;
double x,y,z;
}Cir;
void deal(node a,node b,double k){
double tmp=k*k-1;
double tmpx=a.x-k*k*b.x;
double tmpy=a.y-k*k*b.y;
double tmpz=a.z-k*k*b.z;
double tmp2=k*k*(b.x*b.x+b.y*b.y+b.z*b.z)-(a.x*a.x+a.y*a.y+a.z*a.z);
tmpx/=tmp,tmp2/=tmp;tmpy/=tmp,tmpz/=tmp;
Cir.x=-tmpx;
Cir.y=-tmpy;
Cir.z=-tmpz;
tmp2=Cir.x*Cir.x+Cir.y*Cir.y+Cir.z*Cir.z-tmp2;
Cir.r=sqrt(tmp2);
}
double dis(circle c1,circle c2){
return sqrt((c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y)+(c1.z-c2.z)*(c1.z-c2.z));
}
int main(){
//freopen("data.in","r",stdin);
int t;
scanf("%d",&t);
while(t--){
scanf("%lf%lf%lf",&a.x,&a.y,&a.z);
scanf("%lf%lf%lf",&b.x,&b.y,&b.z);
scanf("%lf%lf%lf",&c.x,&c.y,&c.z);
scanf("%lf%lf%lf",&d.x,&d.y,&d.z);
double k1,k2;
scanf("%lf%lf",&k1,&k2);
deal(a,b,k1);
circle c1=Cir;
deal(c,d,k2);
circle c2=Cir;
double dd=dis(c1,c2);
double ans=0;
if(dd>=c1.r+c2.r){
ans=0;
}else if(dd+c1.r<=c2.r){
ans=(4.0/3.0)*pi*c1.r*c1.r*c1.r;
}else if(dd+c2.r<=c1.r){
ans=(4.0/3.0)*pi*c2.r*c2.r*c2.r;
}else{
double cal=(c1.r*c1.r+dd*dd-c2.r*c2.r)/(2.0*c1.r*dd);
double h=c1.r*(1.0-cal);
ans+=pi*h*h*(c1.r-h/3.0);
cal=(c2.r*c2.r+dd*dd-c1.r*c1.r)/(2.0*c2.r*dd);
h=c2.r*(1.0-cal);
ans+=pi*h*h*(c2.r-h/3.0);
}
printf("%.6lf\n",ans);
}
return 0;
}League of Legends
#include <bits/stdc++.h>
using namespace std;
const int N=5005;
typedef long long ll;
ll f[N][N];
struct Seg{
int l,r;
}p[N],s[N];
int ida,idb;
int big[N];
bool isbig[N];
bool cmp(int A,int B)
{
return A>B;
}
bool cnp(Seg A,Seg B)
{
return A.l<B.l;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].l,&p[i].r);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j||isbig[j]) continue;
if(p[i].l<=p[j].l&&p[j].r<=p[i].r)
{
isbig[i]=true;
break;
}
}
}
for(int i=1;i<=n;i++)
{
if(isbig[i]) big[++idb]=p[i].r-p[i].l;
else s[++ida]=p[i];
}
sort(s+1,s+1+ida,cnp);
sort(big+1,big+1+idb,cmp);
memset(f,-0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=k;i++)
{
deque<int>q;q.push_back(0);
for(int j=1;j<=ida;j++)
{
while(q.size()&&s[q.back()+1].r<=s[j].l) q.pop_back();
if(q.size()) f[i][j]=f[i-1][q.back()]+s[q.back()+1].r-s[j].l;
while(q.size()&&f[i-1][j]+s[j+1].r>=f[i-1][q.front()]+s[q.front()+1].r) q.pop_front();
q.push_front(j);
}
}
ll ans=0,res=0;
for(int i=0;i<=min(k-1,idb);i++)
{
res+=big[i];
if(f[k-i][ida]>=0) ans=max(ans,f[k-i][ida]+res);
}
printf("%lld\n",ans);
return 0;
}
Penguins
#include<bits/stdc++.h>
#define ll long long
const double pi = acos(-1);
using namespace std;
char mpl[25][25],mpr[25][25];
char as[25][25][25][25];//存L,R,U,D
int vis[25][25][25][25];//存步数
int dirl[4][2] = {1,0,0,-1,0,1,-1,0};
int dirr[4][2] = {1,0,0,1,0,-1,-1,0};
char tag[] = "DLRU";
pair<pair<int,int>,pair<int,int> > lst[25][25][25][25];
void check1(int&x1,int&y1,int k){
int u=x1+dirl[k][0];
int v=y1+dirl[k][1];
if(u<1||u>20||v<1||v>20||mpl[u][v]=='#'){
u=x1;
v=y1;
}
x1=u;
y1=v;
}
void check2(int&x2,int&y2,int k){
int u=x2+dirr[k][0];
int v=y2+dirr[k][1];
if(u<1||u>20||v<1||v>20||mpr[u][v]=='#'){
u=x2;
v=y2;
}
x2=u;
y2=v;
}
void bfs(){
queue<pair< pair<int,int>,pair<int,int> > >q;
q.push({{20,20},{20,1}});
as[20][20][20][1]='0';
memset(vis,-1,sizeof(vis));
vis[20][20][20][1]=0;
while(q.size()){
int x1=q.front().first.first,y1=q.front().first.second;
int x2=q.front().second.first,y2=q.front().second.second;
q.pop();
for(int i=0;i<4;i++){
int x3=x1,y3=y1,x4=x2,y4=y2;
check1(x3,y3,i);
check2(x4,y4,i);
if(vis[x3][y3][x4][y4]!=-1)continue;
vis[x3][y3][x4][y4]=vis[x1][y1][x2][y2]+1;
as[x3][y3][x4][y4]=tag[i];
lst[x3][y3][x4][y4]={{x1,y1},{x2,y2}};
q.push({{x3,y3},{x4,y4}});
if(x3== 1 && y3 == 20 && x4 == 1 && y4 == 1) {return;}
}
}
}
vector<char> ans;
int main(){
for(int i=1;i<=20;i++){
cin>>mpl[i]+1;
cin>>mpr[i]+1;
}
bfs();
int xa=1,ya=20,xb=1,yb=1;
printf("%d\n",vis[xa][ya][xb][yb]);
while(1){
ans.push_back(as[xa][ya][xb][yb]);
mpl[xa][ya]='A';
mpr[xb][yb]='A';
int u=lst[xa][ya][xb][yb].first.first,v=lst[xa][ya][xb][yb].first.second,w=lst[xa][ya][xb][yb].second.first,p=lst[xa][ya][xb][yb].second.second;
xa=u;ya=v;xb=w,yb=p;
if(vis[xa][ya][xb][yb]==0){
mpl[xa][ya]='A';
mpr[xb][yb]='A';
break;
}
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++){
printf("%c",ans[i]);
}
cout<<endl;
for(int i=1;i<=20;i++){
printf("%s %s\n",mpl[i]+1,mpr[i]+1);
}
return 0;
}Product of GCDs
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=Phi)&&(x-=Phi))
#define Mod2(x) ((x<0)&&(x+=Phi))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
const int N=8e4+10,M=1e7+30;
int n,m;
ll P,Phi;
int notpri[M+1],pri[M/5],pc;
ll A[N],C[N][32];
ll Calc(ll n){
ll p=n;
for(int i=1;1ll*pri[i]*pri[i]<=n;++i) if(n%pri[i]==0) {
p=p/pri[i]*(pri[i]-1);
while(n%pri[i]==0) n/=pri[i];
}
if(n>1) p=p/n*(n-1);
return p;
}
void init(){
rep(i,2,M) {
if(!notpri[i]) pri[++pc]=i;
for(int j=1;j<=pc && 1ll*i*pri[j]<=M;++j) {
notpri[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
ll Mul(ll x,ll y){
return (__int128)x*y%P;
}
ll qpow(ll x,ll k) {
ll res=1;
for(;k;k>>=1,x=Mul(x,x)) if(k&1) res=Mul(res,x);
return res;
}
int main(){
rep(i,2,M) {
if(!notpri[i]) pri[++pc]=i;
for(int j=1;j<=pc && 1ll*i*pri[j]<=M;++j) {
notpri[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
int t;
cin>>t;
while(t--){
scanf("%d%d%lld",&n,&m,&P);
Phi=Calc(P);
for(int i=0;i<N;i++)A[i]=0;
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);A[x]++;
}
rep(i,0,n) rep(j,*C[i]=1,min(i,m)) C[i][j]=C[i-1][j]+C[i-1][j-1],Mod1(C[i][j]);
long long ans=1;
for(int i=2;i<N;i++){
long long res=0;
if(notpri[i])continue;
for(int x=i;x<N;x*=i){
int c=0;
for(int j=x;j<N;j+=x){
c+=A[j];
}
if(c<m)break;
res=(res+C[c][m])%Phi;
}
if(res)ans=Mul(ans,qpow(i,res));
}
printf("%lld\n",ans);
}
return 0;
}WeChat Walk
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N=200010,M=10010;
typedef pair<int,int> PII;
int n,m,q,B;
int a[N],res[N];
vector<int> g[N],big[N];
vector<PII> e[M];
int main(){
int n,m,q;
cin>>n>>m>>q;
B=sqrt(m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(g[i].size()>B){
for(int j=0;j<g[i].size();j++){
big[g[i][j]].push_back(i);
}
}
}
for(int i=1;i<=q;i++){
int u,w;
scanf("%d%d",&u,&w);
e[a[u]+=w].push_back({u,i});
}
vector<int> f(n+1,q),las(n+1,q),mn(n+1,q);
for(int i=1e4;i>=1;i--){
for(auto [u,t]: e[i]){
for(auto v : big[u]){
mn[v]=min(mn[v],t);
}
las[u]=f[u];f[u]=t;
}
for(auto [u,t]: e[i]){
if(g[u].size()<=B){
int r=las[u];
for(auto v :g[u]){
r=min(r,f[v]);
}
res[u]+=max(0,r-t);
}else{
res[u]+=max(0,min(mn[u],las[u])-t);
}
}
}
for(int i=1;i<=n;i++)cout<<res[i]<<endl;
return 0;
}
