Tutorial is loading...
Setter's code
int n, k, s = 0;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
s += x;
}
for (int ans = 0;; ans++) {
int a = 2 * (s + ans * k);
int b = (2 * k - 1) * (ans + n);
if (a >= b) {
cout << ans;
return 0;
}
}
First accepted Zhigan.
Tutorial is loading...
Setter's code
for (int i = 0; i < n; i++) {
cin >> k[i] >> l[i];
a.push_back(make_pair(min(2 * k[i], l[i]) - min(k[i], l[i]), i));
}
sort(a.rbegin(), a.rend());
long long ans = 0;
for (int i = 0; i < f; i++) {
int pos = a[i].second;
ans += min(2 * k[pos], l[pos]);
}
for (int i = f; i < n; i++) {
int pos = a[i].second;
ans += min(k[pos], l[pos]);
}
cout << ans;
First accepted polygonia.
Tutorial is loading...
Setter's code
st[0] = 1;
for ( int j = 1; j < maxn; j++ )
st[j] = ( 2 * st[j - 1] ) % base;
int n;
scanf ( "%d", &n );
for ( int j = 0; j < n; j++ )
scanf ( "%d", &a[j] );
sort( a, a + n );
int ans = 0;
for ( int j = 1; j < n; j++ ) {
int len = a[j] - a[j - 1];
int cntL = j;
int cntR = n - j;
int add = ( 1LL * ( st[cntL] - 1 + base ) * ( st[cntR] - 1 + base ) ) % base;
ans = ( 1LL * ans + 1LL * len * add ) % base;
}
printf ( "%d\n", ans );
First accepted div2: RaidenEi.
First accepted div1: Lewin.
Tutorial is loading...
Setter's code
int query(int x,int y){
if(x==-1)return 0;
cout<<1<<' '<<x<<' '<<y<<endl;
string ret;
cin>>ret;
return ("TAK"==ret);
}
int get(int l,int r){
if(l>r)return -1;
while(l<r){
int m=(l+r)/2;
if(query(m,m+1)){
r=m;
}else l=m+1;
}
return l;
}
int main() {
int n,k;
cin>>n>>k;
int x=get(1,n);
int y=get(1,x-1);
if(!query(y,x))y=get(x+1,n);
cout<<2<<' '<<x<<' '<<y<<endl;
return 0;
}
First accepted div2: polygonia.
First accepted div1: V--o_o--V.
Tutorial is loading...
Setter's code
ll dp[32][2][2][2];
ll sum[32][2][2][2];
void add(ll &x,ll y){
x+=y;
if(x>=mod)x-=mod;
}
void sub(ll &x,ll y){
x-=y;
if(x<0)x+=mod;
}
ll mul(ll x,ll y){
return x*y%mod;
}
ll pot[32];
ll solve(int x,int y,int z){
if(x<0||y<0||z<0)return 0;
memset(dp,0,sizeof dp);
memset(sum,0,sizeof sum);
vi A,B,C;
rep(j,0,31){
A.pb(x%2);x/=2;
B.pb(y%2);y/=2;
C.pb(z%2);z/=2;
}
reverse(all(A));
reverse(all(B));
reverse(all(C));
dp[0][1][1][1]=1;
sum[0][1][1][1]=0;
rep(i,0,31){
rep(a,0,2)rep(b,0,2)rep(c,0,2){
rep(x,0,2)rep(y,0,2){
int z=x^y;
if(a==1&&A[i]==0&&x==1)continue;
if(b==1&&B[i]==0&&y==1)continue;
if(c==1&&C[i]==0&&z==1)continue;
add(dp[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],dp[i][a][b][c]);
add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],sum[i][a][b][c]);
add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],mul(z<<(30-i),dp[i][a][b][c]));
}
}
}
ll res=0;
rep(a,0,2)rep(b,0,2)rep(c,0,2){
add(res,sum[31][a][b][c]);
add(res,dp[31][a][b][c]);
}
return res;
}
int main(){
int T;
cin>>T;
while(T--){
int x,y,x2,y2,k;
cin>>x>>y>>x2>>y2>>k;
--x;--y;--x2;--y2;--k;
ll res=0;
add(res,solve(x2,y2,k));
sub(res,solve(x2,y-1,k));
sub(res,solve(x-1,y2,k));
add(res,solve(x-1,y-1,k));
cout<<res<<'\n';
}
return 0;
}
First accepted div2: xsup.
First accepted div1: anta.
Tutorial is loading...
Setter's code
struct node {
int prior, sz, dp, add;
node *l, *r;
node ( int x ) {
prior = ( rand() << 15 ) | rand();
// sz = 1;
dp = x;
l = r = NULL;
add = 0;
}
};
typedef node * pnode;
void push( pnode T ) {
T -> dp += T -> add;
if ( T -> l )
T -> l -> add += T -> add;
if ( T -> r )
T -> r -> add += T -> add;
T -> add = 0;
}
void merge( pnode &T, pnode L, pnode R ) {
if ( !L ) {
T = R;
return;
}
if ( !R ) {
T = L;
return;
}
if ( L -> prior > R -> prior ) {
push( L );
merge( L -> r, L -> r, R );
T = L;
return;
}
push( R );
merge( R -> l, L, R -> l );
T = R;
}
void split( pnode T, int value, pnode &L, pnode &R ) {
if ( !T ) {
L = R = NULL;
return;
}
push( T );
if ( T -> dp >= value ) {
split( T -> l, value, L, T -> l );
R = T;
return;
}
split( T -> r, value, T -> r, R );
L = T;
}
int findBegin( pnode T ) {
push( T );
if ( !T -> l )
return T -> dp;
return findBegin( T -> l );
}
int findMax( pnode T, int n ) {
if ( !T )
return 0;
push( T );
return findMax( T -> l, n ) + findMax( T -> r, n ) + ( T -> dp <= inf ? 1 : 0 );
}
pair < int, int > a[maxn];
pnode T = new node( 0 );
pnode L = NULL;
pnode M = NULL;
pnode R = NULL;
pnode rubbish = NULL;
void solve() {
int n;
scanf ( "%d", &n );
for ( int j = 1; j <= n; j++ )
scanf ( "%d%d", &a[j].f, &a[j].s );
for ( int j = 1; j <= n; j++ )
merge( T, T, new node( inf + j ) );
for ( int j = 1; j <= n; j++ ) {
split( T, a[j].f, L, R );
split( R, a[j].s, M, R );
if ( M )
M -> add += 1;
int cnt = findBegin( R );
split( R, cnt + 1, rubbish, R );
merge( T, L, new node( a[j].f ) );
merge( T, T, M );
merge( T, T, R );
}
printf ( "%d\n", findMax( T, n ) - 1 );
}
First accepted: ksun48.
Tutorial is loading...
Setter's code
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <numeric>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename T>
T nextInt() {
T x = 0, p = 1;
char ch;
do { ch = getchar(); } while(ch <= ' ');
if (ch == '-') {
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * p;
}
const int maxN = (int)2e5 + 10;
const int maxL = 17;
const int INF = (int)1e9;
const int mod = (int)1e9 + 7;
const ll LLINF = (ll)1e18 + 5;
int mul(int x, int y) {
return 1LL * x * y % mod;
}
void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
void sub(int &x, int y) {
x -= y;
if (x < 0) x += mod;
}
int n;
vector <int> g[maxN];
vector <int> d[maxN];
vector <int> coefs[maxN];
int phi[maxN];
int inv[maxN];
int a[maxN];
int tmp[maxN];
void productToTmp(int a, int b) {
for (size_t it = 0; it < d[a].size(); it++) {
for (size_t jt = 0; jt < d[b].size(); jt++) {
int x = d[a][it];
int cx = coefs[a][it];
int y = d[b][jt];
int cy = coefs[b][jt];
add(tmp[x * y], mul(cx, cy));
}
}
}
void precalc() {
inv[1] = 1;
for (int i = 1; i < maxN; ++i) {
phi[i] = i;
if(i > 1) inv[i] = mul(mod - mod / i, inv[mod % i]);
}
for (int i = 1; i < maxN; ++i) {
for (int j = i; j < maxN; j += i) {
d[j].push_back(i);
if (j != i) phi[j] -= phi[i];
}
}
for (int i = 1; i < maxN; ++i) {
coefs[i].resize(d[i].size());
}
coefs[1][0] = 1;
for (int x = 2; x < maxN; x++) {
if ((int)d[x].size() == 2) {
coefs[x][0] = 1;
coefs[x][1] = inv[x - 1];
} else {
int lp = d[x][1];
int z = x;
while (z % lp == 0) {
z /= lp;
}
for (int y: d[x]) {
tmp[y] = 0;
}
productToTmp(lp, z);
for (size_t it = 0; it < d[x].size(); it++) {
coefs[x][it] = tmp[d[x][it]];
}
}
}
}
int nodes[maxN];
int len = 0;
int sz[maxN];
int blocked[maxN];
int level[maxN];
int anc[maxN];
void calc_sizes(int v, int p = -1) {
nodes[len++] = v;
sz[v] = 1;
anc[v] = p;
for (int x: g[v]){
if (blocked[x] || x == p) continue;
calc_sizes(x, v);
sz[v] += sz[x];
}
}
int sum_phi[maxN];
int list_len;
int list[maxN];
int depth[maxN];
void get_list(int v, int par = -1, int dpth = 1) {
list[list_len] = v;
depth[list_len++] = dpth;
for (int x: g[v]) {
if (par == x || blocked[x]) continue;
get_list(x, v, dpth + 1);
}
}
int sum[maxN];
int calc(int value) {
int cur = 0;
for(size_t i = 0; i < d[value].size(); ++i) {
int x = d[value][i];
add(cur, mul(sum_phi[x], coefs[value][i]));
}
return mul(cur, phi[value]);
}
int total = 0;
void solve(int root) { //root is a centroid
for (int i = 0; i < len; ++i) {
int u = nodes[i];
int y = a[u];
for (int x: d[y]) {
add(sum_phi[x], phi[y]);
}
}
for (int child: g[root]) {
if (blocked[child]) continue;
list_len = 0;
get_list(child, root);
{
//excluding everything which can be counted twice
for(int i = 0; i < list_len; ++i) {
int u = list[i];
int y = a[u];
for(int x: d[y]) {
sub(sum_phi[x], phi[y]);
}
}
}
{
for (int i = 0; i < list_len; ++i) {
int u = list[i];
int d = depth[i];
int value = a[u];
add(total, mul(d, calc(value)));
}
}
{
//including back
for(int i = 0; i < list_len; ++i) {
int u = list[i];
int y = a[u];
for(int x: d[y]) {
add(sum_phi[x], phi[y]);
}
}
}
}
//clear
for (int i = 0; i < len; ++i) {
int u = nodes[i];
int y = a[u];
for (int x: d[y]) {
sum_phi[x] = 0;
}
}
}
void build(int v, int lev) {
len = 0;
calc_sizes(v);
int centroid = -1;
for (int i = 0; i < len; ++i) {
int u = nodes[i];
int maxChildSize = len - sz[u];
for (int x: g[u]) {
if (x != anc[u] && !blocked[x]) {
maxChildSize = max(maxChildSize, sz[x]);
}
}
if (maxChildSize <= len / 2) {
centroid = u;
}
}
blocked[centroid] = true;
level[centroid] = lev;
solve(centroid);
for (int x: g[centroid]) {
if (blocked[x]) continue;
build(x, lev + 1);
}
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
precalc();
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
--x; --y;
g[x].push_back(y);
g[y].push_back(x);
}
build(0, 0);
total = mul(total, inv[n]);
total = mul(total, inv[n - 1]);
total = mul(total, 2);
cout << total << endl;
return 0;
}
First accepted: radoslav11.