Setter: MesbahTanvir Alternate Writer: prophet_ov_darkness, s_h_shahin
Editorial
This problem actually reflect the josephus problem.
The main part of this problem is to find Number of possible Y such that josephus(Y,2) = X .
After finding this rest part is obvious calculation.
Let’s see first few values of josephus(i,2): 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15
We can see that there is a nice pattern here. josephus(n,2) is an increasing odd sequence that restarts with josephus(n,2) = 1 whenever the index n is a power of 2.
First we will find minimum value of p such that josephus(p,2) = X. we can do this in O(log n) , because for every q>0 josephus(2^q-1,2) = 2q^-1 and josephus(2^q,2) = 1. So we can run loop through q >= 0 and find highest value of q such that josephus(2^q-1,2) < X. From the pattern it is obvious that the p lies between 2^q and ** 2^(q+1) — 1**. As this pattern is an increasing odd sequence a few calculation enough to find p from q.
Now we know the minimum value of p such that josephus(p,2) = X if the first minimum value of p is a and the second minimum value is b, then it is true that b — a is power of 2 and this is true for next possible values of p. From all these observation we can find all possible Y in range [1,N] such that josephus(Y,2) = X. and there are at most log(N) values.
Complexity: O(log n)
Solution Code
ISwearIsMyLastContest
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAXN 100005
using namespace std;
vector < ll > survivalList(ll id,ll n){
ll i ,firstOccur , p , q,Occur;
vector < ll > vec;
if( ( id & 1 )==0 ) return vec;
for( i = 1 ; ; i ++ ){
if( ( ( 1LL<<i ) - 1 ) >= id){
p = i - 1;
q = ( 1LL << i) - 1 ;
break;
}
}
firstOccur = (q) - ( q - id ) / 2;
Occur = firstOccur ;
while(Occur <= n){
vec.pb( Occur );
Occur += (1LL<<p);
p++;
}
return vec;
}
int main(int argc , char *args[])
{
int tc,cs=0;
scanf("%d",&tc);
while(tc--){
long long x, l, n,ans_event=0,total_event=0;
scanf("%lld %lld %lld",&x,&l,&n);
total_event = n-l+1;
ans_event = max(0LL, x - l );
auto vec = survivalList(x,n);
for(auto v : vec){
if( v >=l and v<= n) ans_event ++;
}
long long gcd = __gcd(ans_event,total_event);
ans_event/= gcd;
total_event/=gcd;
printf("Case %d: %lld/%lld\n",++cs,ans_event,total_event);
}
return 0;
}
s_h_shahin
...
prophet_ov_darkness
/*
* Alternate solution for ST3
* by Sourav Sen Tonmoy
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define DB(x) cerr << #x << " = " << x << endl
#define OK cerr << "ok\n"
inline LL lg2(LL x) {
LL ret = 0;
while(x >= 2) {
x >>= 1ll;
ret++;
}
return ret;
}
// returns number of time x stays alive for all l in range [1, n]
inline LL f(LL n, LL x) {
if(n == 0) return 0;
LL ret = min(x-1, n);
if(x%2 == 0) return ret;
LL what = lg2(x);
LL pos1 = 1ll << what;
LL offset = (x-1)/2;
LL firstAppear = pos1+offset;
for(LL i=firstAppear; i<=n; i += pos1, pos1 <<= 1ll) ret++;
return ret;
}
inline LL solve(LL x, LL l, LL n) {
return f(n, x) - f(l-1, x);
}
int main() {
// assert(freopen("task_3_in.txt", "r", stdin));
// assert(freopen("test.txt", "w", stdout));
int test, kase=1;
LL x, l, n;
assert(scanf("%d", &test) == 1);
assert(1<=test && test <= 10400);
while(test--) {
assert(scanf("%lld %lld %lld", &x, &l, &n) == 3);
assert(1 <= x && x <= 1000000000000000);
assert(1 <= n && n <= 1000000000000000);
assert(1 <= l && l <= 1000000000000000);
assert(x <= n);
assert(l <= n);
LL up = solve(x, l, n);
LL dn = n-l+1;
LL gg = __gcd(up, dn);
up /= gg;
dn /= gg;
if(up == 0) dn = 1;
printf("Case %d: %lld/%lld\n", kase++, up, dn);
}
return 0;
}
Setter: Tanzir5 Alternate Writer: bertho_coder, Alpha_Q
Editorial
If constraint where
0 ≤ n, m ≤ 105 Q = 0 1 ≤ xi ≤ yi ≤ 10^5 **** We could do this, It is actually easier to find out how many flights don't intersect with each other. If you can calculate that then you can subtract it from the total number of possible pairs and get the answer.
Store two vectors for each of the list. For list 1, store two vectors start[] and end[] for both lists. For list 1, start[] should contain starting points of ranges and end[] should contain ending points of ranges of flights of list 1. Sort both of them. Now for each flight of list 2 with a range (x,y), find the number of elements in end[] who are less than x. Also find the number of elements in start[] who are greater than y. You can do these by binary searching. These are the flights of list 1 that do not have any common region with (x,y). And all other flights must have some common part with the range (x,y).
For actual constraint we can do this,
Same idea as above. You just need to use a different data structure this time. Store two segment trees, namely start[] and end[], for each of the two lists of flights. For list 1, start[i] should be equal to the number of flights whose range starts at i'th hour. end[i] should be equal to the number of flights whose range ends at i'th hour. So when you get an update for a new flight to be inserted in list 2 with a range of x to y. You should check the value of the range 1 to x-1 in end[] and value of the range y+1 to MAXVAL in start[]. These are the flights who have a starting point later than y or a ending point lesser
Solution Code
Maxon5
#include<bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define D(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << '\n'
#define DDD(x,y,z) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << '\n'
#define DBG cerr << __LINE__ << ": Hi" << '\n'
#define MAX 600000
#define endl '\n'
typedef pair<int,int> pii;
typedef long long int LL;
LL ans;
struct data{
LL lazy, val;
};
struct queryData{
int type, x, y;
};
vector<queryData>query;
struct segmentTree{
data tree[MAX*4+10];
void propagate(int node, int st, int ed)
{
int lft = 2*node, rght = 2*node+1, mid = (st+ed)/2;
tree[lft].lazy += tree[node].lazy;
tree[rght].lazy += tree[node].lazy;
tree[lft].val += (mid-st+1)*tree[node].lazy;
tree[rght].val += (ed - (mid+1)+1) * tree[node].lazy;
tree[node].lazy = 0;
}
void update(int node, int st, int ed, int i, int j)
{
if(j < st || i > ed)
return;
if(i <= st && ed <= j)
{
tree[node].lazy++;
tree[node].val += (ed-st+1);
return;
}
if(tree[node].lazy)
propagate(node, st, ed);
int lft = 2*node, rght = 2*node+1, mid = (st+ed)/2;
update(lft, st, mid, i, j);
update(rght, mid+1, ed, i, j);
tree[node].val = tree[lft].val + tree[rght].val;
}
LL query(int node, int st, int ed, int i, int j)
{
if(j < st || i > ed)
return 0;
if(i <= st && ed <= j)
return tree[node].val;
if(tree[node].lazy)
propagate(node, st, ed);
int lft = 2*node, rght = 2*node+1, mid = (st+ed)/2;
LL ret = query(lft, st, mid, i, j);
ret += query(rght, mid+1, ed, i, j);
return ret;
}
};
struct flightData{
segmentTree point, range;
vector<pii>flight;
}F[2];
map<int,int>M;
int total;
void compress()
{
int cnt = 0;
for(auto &m: M)
m.yy = ++cnt;
for(int i = 0; i<2; i++)
for(auto &v: F[i].flight)
v.xx = M[v.xx], v.yy = M[v.yy];
for(auto &v: query)
v.x = M[v.x], v.y = M[v.y];
total = cnt;
D(total);
}
inline void add(pii f, int type)
{
// D(type);
int st = f.xx, ed = f.yy;
LL nw = F[type^1].range.query(1,1,total,st,st);
nw += F[type^1].point.query(1,1,total,st+1,ed);
ans += nw;
F[type].point.update(1,1,total,st,st);
F[type].range.update(1,1,total,st,ed);
}
int main()
{
// freopen("inputSubtask3.txt", "r", stdin);
// freopen("outputSubtask3.txt", "w", stdout);
// freopen("sample.txt", "r", stdin);
// freopen("outputSample.txt", "w", stdout);
std::ios::sync_with_stdio(false);
int t, n[2], x, y, q, type;
assert(cin >> t);
assert( 1<= t && t <= 100);
for(int cs = 1; cs<=t; cs++)
{
D(cs);
query.clear();
M.clear();
ans = 0;
for(int type = 0; type < 2; type++)
{
F[type].flight.clear();
memset(F[type].point.tree, 0, sizeof(F[type].point.tree));
memset(F[type].range.tree, 0, sizeof(F[type].range.tree));
assert(cin >> n[type]);
assert( 0<=n[type] && n[type] <=100000);
for(int i = 1; i<=n[type]; i++)
{
assert(cin >> x >> y );
assert( x <= y);
assert( 1<=x && x <= 1000000000);
assert( 1<=y && y <= 1000000000);
M[x] = M[y] = true;
F[type].flight.push_back({x,y});
}
}
assert(cin >> q);
for(int i = 1; i<=q; i++)
{
assert(cin >> type >> x >> y );
assert(1 <= type && type <= 2);
assert( x <= y);
assert( 1<=x && x <= 1000000000);
assert( 1<=y && y <= 1000000000);
query.push_back({type-1,x,y});
M[x] = M[y] = true;
}
compress();
cout << "Case " << cs << ": ";
for(int type = 0; type < 2; type++)
{
for(int i = 0; i<n[type]; i++)
add(F[type].flight[i], type);
}
cout << ans << endl;
for(auto u: query)
add({u.x, u.y}, u.type), cout << ans << endl;
}
// assert((cin >> t) == 0);
}
101864C - BACS, Scoundrel Shopkeeper and Contiguous Sequence
Setter: Imran_Bin_Azad,raihatneloy Alternate Writer: bertho_coder, Imran_Bin_Azad, flash_7, aminul
Editorial
This is an easy problem. So no hint for this problem.
Setter: s_h_shahin Alternate Writer: MesbahTanvir, aminul
Editorial
Tag : DSU on Tree/ Mo’s Algorithm
Let BL[i] denote the beauty value of the level i. Beauty of the total tree is maximum value from the BL array.
DSU on Tree Technique
Now, the subtree removal operation can be done using DSU on Tree algorithm which does some operation for a subtree in O(N * logN). While removing any node from the total solution, we also need to keep track of the maximum value of the BL array. As there is continuous addition and removal operation in DSU on Tree, we need extra** O(logN)**. Overall complexity per test case : O(N * logN * logN)
Mo’s Algorithm
The subtree removal can also be done using Mo’s algorithm. We run a dfs first. If we build an array A of size N and A[i] holds a the node having starting time i, subtree of every node in the tree can be represented as a continuous interval of the array. Mo’s algorithm can process continuous intervals. There will be N-1 intervals to process. Complexity will be O(N * sqrtN). For keeping track of the maximum value of the BL array, we will need extra O(logN). Overall complexity per test case : O(N * sqrtN * logN)
Solution Code
s_h_shahin
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100010;
vector <int> G[MAX];
int sub[MAX], L[MAX];
int B[MAX], sum[MAX], ans[MAX];
int maxDepth;
int tree[4*MAX];
void update(int n,int st,int ed,int id,int v)
{
if(id>ed || id<st) return;
if(st==ed && ed==id)
{
tree[n] = v;
return;
}
int mid = (st+ed)/2;
update(2*n,st,mid,id,v);
update(2*n+1,mid+1,ed,id,v);
tree[n] = max(tree[2*n],tree[2*n+1]);
}
int query(int n,int st,int ed,int i,int j)
{
if(st>=i && ed<=j) return tree[n];
int mid = (st+ed)/2;
if(mid<i) return query(2*n+1,mid+1,ed,i,j);
else if(mid>=j) return query(2*n,st,mid,i,j);
else return max(query(2*n,st,mid,i,j),query(2*n+1,mid+1,ed,i,j));
}
void calcSubsize(int node,int par,int level)
{
sub[node] = 1;
L[node] = level;
sum[level] += B[node];
maxDepth = max(maxDepth,level);
for(auto v: G[node])
{
if(v==par) continue;
calcSubsize(v,node,level+1);
sub[node] += sub[v];
}
}
void add(int node,int par,int x,int bigChild=-1)
{
sum[L[node]] += x*B[node];
update(1,1,maxDepth,L[node],sum[L[node]]);
for(auto v : G[node])
{
if(v==par or v==bigChild) continue;
add(v,node,x);
}
}
void dfs(int node,int par,bool keep)
{
int bigChild = -1;
for(auto v : G[node])
{
if(v==par) continue;
if( bigChild ==-1 or sub[bigChild] < sub[v] ) bigChild = v;
}
for(auto v : G[node])
{
if(v==par or v==bigChild) continue;
dfs(v,node,0);
}
if(bigChild!=-1) dfs(bigChild,node,1);
add(node,par,1,bigChild);
ans[node] = query(1,1,maxDepth,1,maxDepth);
if(!keep) add(node,par,-1);
}
int main()
{
// freopen("input3.txt","r",stdin);
// freopen("output3.txt","w",stdout);
double start_clock = clock();
int t,T,n,u,v,w,x;
scanf("%d",&T);
for(int t=1; t<=T; t++)
{
scanf("%d",&n);
cerr << t << " " << n << endl;
for(int i=1; i<=n; i++) scanf("%d",&B[i]);
for(int i=2; i<=n; i++)
{
u = i;
scanf("%d",&v);
G[u].push_back(v);
G[v].push_back(u);
}
maxDepth = 0;
calcSubsize(1,-1,1);
for(int i=1; i<=n; i++) B[i] *= -1;
for(int i=1; i<=maxDepth; i++) update(1,1,maxDepth,i,sum[i]);
dfs(1,-1,0);
for(int i=2; i<=n; i++)
{
printf("%d\n",ans[i]);
}
memset(tree,0,sizeof(tree));
memset(sum,0,sizeof(sum));
for(int i=1; i<=n; i++) G[i].clear();
}
double end_clock = clock();
cerr<< setprecision(10) << fixed << (end_clock - start_clock) / CLOCKS_PER_SEC <<endl;
return 0;
}
ISwearItIsMyLastContest
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define MAXN 100010
vector < int > ed[MAXN] ;
int n , ans[MAXN] , b[MAXN] , sum[MAXN],subSize[MAXN] , height[MAXN];
multiset < int > sums;
void Clear(){
sums.clear();
assert(sums.size()==0);
for(int i=0;i<MAXN;i++) ed[i].clear();
memset(b,0,sizeof(b));
memset(ans,0,sizeof(ans));
memset(sum,0,sizeof(sum));
memset(subSize,0,sizeof(subSize));
}
void preCal(int u, int p, int h =0){
height[u] = h;
sum[h] += b[u];
for(auto v: ed[u]){
if( v == p ) continue;
preCal(v,u,h+1);
subSize[u] += subSize[v];
}
subSize[u]++;
}
void addOnTree(int u , int p, int bigChild , int add){
if(add){
sums.erase(sums.find(sum[ height[u] ]));
sum[ height[u] ] -=b[u];
sums.insert(sum[ height[u] ]);
}
else {
sums.erase(sums.find(sum[ height[u] ]));
sum[ height[u] ] += b[u];
sums.insert(sum[ height[u] ]);
}
for(auto v: ed[u]){
if(v!=p and v!=bigChild){
addOnTree(v,u,-1,add);
}
}
}
void storeAns(int u){
auto it = sums.end();it--;
ans[u] = *it;
}
void treeDsu(int u, int p,int keep){
int bigChild =-1;
for(auto v: ed[u]){
if(v==p) continue;
if(bigChild==-1) bigChild=v;
if(subSize[v]>subSize[bigChild]) bigChild = v;
}
for(auto v: ed[u]){
if(v==p or v==bigChild) continue;
treeDsu(v,u,false);
}
if( bigChild != -1) treeDsu(bigChild,u,true);
addOnTree(u,p,bigChild,true);
storeAns(u);
if(!keep) addOnTree(u,p,-1,false);
}
void solve(){
preCal(1,0);
for(int i=0;i<n;i++) sums.insert(sum[i]);
treeDsu(1,0,0);
}
int main(int argc,char *args[]){
double start_clock = clock();
int tc;
scanf("%d",&tc);
while(tc--){
Clear();
scanf("%d",&n);
for( int i = 1 ; i <= n ; i++) {
scanf("%d",b+i);
assert(0 <= b[i] <= 10000);
}
for(int i = 2 ; i <= n; i++){
int u;
scanf("%d",&u);
assert(u>=1 and u<=n);
ed[i].pb(u) ; ed[u].pb(i);
}
solve();
for(int i = 2; i<= n; i++){
printf("%d\n",ans[i]);
};
}
double end_clock=clock();
cerr<<(end_clock-start_clock)/CLOCKS_PER_SEC<<endl;
return 0;
}
aminul
/**
* Created by Aminul on 7/11/2018.
*/
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class Another_Tree_Query_Problem__ST_3 {
public static void main(String[] args) throws Exception {
new Thread(null ,new Runnable(){
public void run(){try{solveIt();} catch(Exception e){e.printStackTrace();}}
},"Main",1<<25).start();
}
public static void solveIt() throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter pw = new PrintWriter(System.out);
int test = in.nextInt();
for(int t = 1; t <= test; t++) {
int n = in.nextInt();
g = genList(n+1);
for (int i = 1; i <= n; i++) {
arr[i] = in.nextInt();
levelSum[i] = 0;
}
for (int i = 2; i <= n; i++) {
int u = in.nextInt();
g[u].add(i);
}
int height = calcLevelSum(1, 0, 1);
pst = new PersistentSegmentTree(height);
dfs(1, 0);
for (int i = 2; i <= n; i++) {
pw.println(ans[i]);
}
}
pw.close();
}
static int N = 100000+50;
static List<Integer> g[];
static HashMap<Integer, Integer> map[] = new HashMap[N];
static int level[] = new int[N], arr[] = new int[N], ans[] = new int[N], levelSum[] = new int[N];
static int seg[][] = new int[3][(int)5e6], roots[] = new int[N];
static PersistentSegmentTree pst;
static int subTreeHeight[] = new int[N];
static int calcLevelSum(int u, int p, int l){
int maxLevel = 0;
levelSum[l] += arr[u];
level[u] = l;
for(int v : g[u]){
if(v != p){
maxLevel = max(maxLevel, calcLevelSum(v, u, l+1));
}
}
return subTreeHeight[u] = maxLevel+1;
}
static void dfs(int u, int p){
int maxLevel = 0, maxNode = -1;
for(int v : g[u]){
if(v != p){
dfs(v, u);
if(subTreeHeight[v] > maxLevel){
maxLevel = level[v];
maxNode = v;
}
}
}
if(maxNode != -1){
map[u] = map[maxNode];
roots[u] = roots[maxNode];
}
else{
map[u] = new HashMap<>();
roots[u] = roots[0];
}
map[u].put(level[u], arr[u]);
roots[u] = pst.update(roots[u], level[u], arr[u]);
for(int v : g[u]){
if(v != p && v != maxNode){
for(Map.Entry<Integer, Integer> entry : map[v].entrySet()){
map[u].put(entry.getKey(), map[u].getOrDefault(entry.getKey(), 0) + entry.getValue());
roots[u] = pst.update(roots[u], entry.getKey(), entry.getValue());
}
}
}
ans[u] = seg[0][roots[u]];
}
static class PersistentSegmentTree{
int id, n;
PersistentSegmentTree(int n){
this.n = n;
init();
roots[0] = build(1, n);
}
void init(){
id = 1;
seg[1][0] = seg[1][1] = seg[2][1] = 0;
}
int build(int s, int e){
if(s == e){
seg[0][++id] = levelSum[s];
return id;
}
if(s > e) return 0;
int m = (s+e)/2;
int l = build(s, m), r = build(m+1, e);
++id;
seg[0][id] = max(seg[0][l], seg[0][r]);
seg[1][id] = l; seg[2][id] = r;
return id;
}
int update(int r, int pos, int v){
return update(r, 1, n, pos, v);
}
int update(int p, int s, int e, int pos, int v){
if(s == pos && e == pos){
seg[0][++id] = seg[0][p] - v;
return id;
}
if(s > e || s > pos || e < pos) return p;
int m = (s+e)/2;
int l = update(seg[1][p], s, m, pos, v),
r = update(seg[2][p], m+1, e, pos, v);
++id;
seg[0][id] = max(seg[0][l], seg[0][r]);
seg[1][id] = l; seg[2][id] = r;
return id;
}
}
static <T>List<T>[] genList(int n){
List<T> list[] = new List[n];
for(int i = 0; i < n; i++) list[i] = new ArrayList<T>();
return list;
}
static void debug(Object...obj) {
System.err.println(Arrays.deepToString(obj));
}
static class FastReader {
InputStream is;
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
static final int ints[] = new int[128];
public FastReader(InputStream is){
for(int i='0';i<='9';i++) ints[i]=i-'0';
this.is = is;
}
public int readByte(){
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
public boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
public int skip() {
int b;
while((b = readByte()) != -1 && isSpaceChar(b));
return b;
}
public String next(){
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public int nextInt(){
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = (num<<3) + (num<<1) + ints[b];
}else{
return minus ? -num : num;
}
b = readByte();
}
}
public long nextLong() {
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = (num<<3) + (num<<1) + ints[b];
}else{
return minus ? -num : num;
}
b = readByte();
}
}
public double nextDouble() {
return Double.parseDouble(next());
}
/* public char nextChar() {
return (char)skip();
}*/
public char[] next(int n){
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
/*private char buff[] = new char[1005];
public char[] nextCharArray(){
int b = skip(), p = 0;
while(!(isSpaceChar(b))){
buff[p++] = (char)b;
b = readByte();
}
return Arrays.copyOf(buff, p);
}*/
}
}
Setter: SkullKnight Alternate Writer: Alpha_Q
Editorial
When K > N, ans = 0 (since you can’t take two person from the same team)
Otherwise, you can fix K teams from N teams in NcK ways. These K teams will each give 1 member to our new team. There are M members in each team and K teams in total.
So the final answer is (NcK) * (M^K)
You can calculate it using factorials (precompute the factorials upto 10^7 at the beginning). Also you will need to use Mod Inverse here.
To calculate M^K efficiently, you need to use bigmod algorithm.
Complexity: O(N)
Solution Code
Alpha_Q
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic warning "-std=c++11"
typedef long long ll;
const int N = 10000005;
const int MOD = 1e9 + 7;
int t, n, m;
ll k, f[N], inv[N];
ll bigMod (ll a, ll e) {
if (e == -1) e = MOD - 2;
ll ret = 1;
while (e) {
if (e & 1) ret *= a, ret %= MOD;
a *= a, a %= MOD, e >>= 1;
}
return ret;
}
inline ll comb (int x, int y) {
return f[x] * (inv[y] * inv[x - y] % MOD) % MOD;
}
int main() {
f[0] = 1;
for (int i = 1; i < N; ++i) {
f[i] = i * 1LL * f[i - 1] % MOD;
}
inv[N - 1] = bigMod(f[N - 1], -1);
for (int i = N - 1; i; --i) {
inv[i - 1] = i * 1LL * inv[i] % MOD;
}
scanf("%d", &t);
assert(1 <= t and t <= 1000);
while (t--) {
scanf("%d %d %lld", &n, &m, &k);
assert(2 <= n and n <= 10000000);
assert(2 <= m and m <= 10000000);
assert(1 <= k and k <= n * 1LL * m);
if (k > n) {
puts("0");
continue;
}
ll ans = comb(n, k) * bigMod(m, k) % MOD;
printf("%lld\n", ans);
}
return 0;
}
Setter: kimbbakar Alternate Writer: Alpha_Q
Editorial
We can use an array to mark all the position occupied or not. After each update, we can update the position x,y separately. For counting number of holes, in each query, we just iterate over the mark array.
Complexity: O(T*N*Q) [Will get TLE]
Similar to the above solution, we will use a mark array here. For counting number of holes, we can maintain a global count variable. In each query, we will just check adjacent position before removing or adding a player.
Complexity: O(T*Q) [This will also get TLE ]
Rather than keeping which position are occupied, we will keep which segments are occupied.
When we will remove a player, we need to update the segment where it belongs. Same goes for adding a player. We might need to merge two new segments or increase the length of a segment.
Using STL set, we can do this job easily.
Complexity: O(T*log2(n)*Q )
Solution Code
kimbbakar
#include<bits/stdc++.h>
#define pause system("pause");
#define FOR(s,e,inc) for(int i=s;i<=e;i+=inc)
#define mod 1000000007
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())//vector must be sorted
#define inf 1<<30
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define F first
#define S second
#define sz(x) ((int)x.size())
#define sqr(x) ( (x)* (x) )
#define eps 1e-9
#define lcm(x,y) (abs(x) /gcd(x,y))* abs(y)
#define on(x,w) x|(1<<w)
#define check(x,w) (x&(1<<w))
#define all(x) (x).begin(),(x).end()
#define pf printf
#define sf scanf
#define pi acos(-1.0)
#define reset(x,v) memset(x,v,sizeof(x));
#define AND &&
#define OR ||
#define what_is(x) cerr<<#x<<" is "<<x<<"\n";
typedef long long ll;
typedef unsigned long long llu;
using namespace std;
template<class T>
inline T mod_v(T num)
{
if(num>=0)
return num%mod;
else
return (num%mod+mod)%mod;
}
template<class T>
inline T gcd(T a,T b)
{
a=abs(a);
b=abs(b);
while(b) b ^= a ^= b ^= a %= b;
return a;
}
template<class T>
T fast_pow(T n , T p)
{
if(p==0) return 1;
if(p%2)
{
T g=mod_v ( mod_v(n) * mod_v(fast_pow(n,p-1)) );
return g;
}
else
{
T g=fast_pow(n,p/2);
g=mod_v( mod_v(g) * mod_v(g) ) ;
return g;
}
}
template<class T>
inline T modInverse(T n)
{
return fast_pow(n,mod-2);
}
bool equalTo ( double a, double b ){ if ( fabs ( a - b ) <= eps ) return true; else return false; }
bool notEqual ( double a, double b ){if ( fabs ( a - b ) > eps ) return true; else return false; }
bool lessThan ( double a, double b ){ if ( a + eps < b ) return true; else return false; }
bool lessThanEqual ( double a, double b ){if ( a < b + eps ) return true; else return false;}
bool greaterThan ( double a, double b ){if ( a > b + eps ) return true;else return false;}
bool greaterThanEqual ( double a, double b ){if ( a + eps > b ) return true;else return false;}
#define debug(args...) {dbg,args; cerr<<endl;}
struct debugger{
template<typename T> debugger& operator , (const T& v){
cerr<<v<<" ";
return *this;
}
}dbg;
int nextInt() { int n; scanf("%d", &n); return n; }
long long nextLong() { long long n; scanf("%lld", &n); return n; }
void print(int n){ printf("%d", n); }
void println(int n){ printf("%d\n", n); }
void println(long long n){ printf("%lld\n", n); }
template<class T>
inline int in(register T& num)
{
register char c=0;
num=0;
bool n=false;
while(c<33)c=getchar();
while(c>33){
if(c=='-')
n=true;
else num=num*10+c-'0';
c=getchar();
}
num=n?-num:num;
return 1;
}
/******* ! Code start from here ! *******/
int main()
{
// std::ios_base::sync_with_stdio(false);
#ifdef kimbbakar
freopen ( "E:/Code/in.txt", "r", stdin );
freopen ( "E:/Code/out.txt", "w", stdout );
#endif
int t,tcase=1;
int N,K,Q;
scanf("%d",&t);
while(t--){
scanf("%d %d %d",&N,&K,&Q);
assert(1<=N and N<=1e9);
assert(K<N);
assert(Q<=1e5);
set<pair<int,int> > segment;
segment.insert({1,-1});
segment.insert({K,1});
segment.insert({-inf,-1});
segment.insert({-inf,1});
segment.insert({inf,-1});
segment.insert({inf,1});
int x,y;
int hole = 1;
std::set<pair<int,int> >::iterator itlow,itup;
pf("Case %d:\n",tcase++);
while(Q--){
scanf("%d %d",&x,&y);
assert(1<=x and x<=N);
assert(1<=y and y<=N);
itlow = segment.lower_bound({x,-1} ) ;
if((*itlow).S==1) itlow--;
itup = segment.upper_bound({(*itlow).F,-1} ) ;
/* what_is((*itlow).F)
what_is((*itup).F)
what_is((*itlow).S)
what_is((*itup).S)*/
assert(!((*itlow).S==1 or (*itup).S==-1));
assert(!( ( (*itlow).F> (*itup).F ) or ( (*itlow).F== (*itup).F and (*itlow).S>= (*itup).S ) ));
assert(! ((*itlow).F>x or (*itup).F<x) );
if((*itlow).F==(*itup).F){
segment.erase(itlow);
segment.erase(itup);
if(x!=1 and x!=N)
hole--;
}
else if((*itlow).F==x) {
segment.erase(itlow);
segment.insert({x+1,-1 } );
if(x==1 or x==N)
hole++;
}
else if((*itup).F==x) {
segment.erase(itup);
segment.insert({x-1,1 } );
if(x==1 or x==N)
hole++;
}
else{
segment.insert({x-1,1 } );
segment.insert({x+1,-1 } );
hole++;
}
// what_is(hole)
itlow = segment.find({y-1,1} ) ;
itup = segment.find({y+1,-1} ) ;
if(itlow!=segment.end() and itup!=segment.end()){
segment.erase(itlow);
segment.erase(itup);
hole--;
}
else if(itlow!=segment.end()){
segment.erase(itlow);
segment.insert({y,1});
if(y==1 or y==N)
hole--;
}
else if(itup!=segment.end()){
segment.erase(itup);
segment.insert({y,-1});
if(y==1 or y==N)
hole--;
}
else{
segment.insert({y,-1});
segment.insert({y,1});
if(y!=1 and y!=N)
hole++;
}
pf("%d\n",hole);
/* for(auto pt:segment)
pf("| %d, %d |",pt.F,pt.S);
pf("\n");*/
}
}
return 0;
}
Alpha_Q
include<bits/stdc++.h>
define inf 1<<30
define F first
define S second
define pf printf
using namespace std;
int main() { // freopen("sample.in", "r", stdin); int t,tcase=1;
int N,K,Q;
scanf("%d",&t);
while(t--){
scanf("%d %d %d",&N,&K,&Q);
set<pair<int,int> > segment;
segment.insert(make_pair(1,-1));
segment.insert(make_pair(K,1));
segment.insert(make_pair(-inf,-1));
segment.insert(make_pair(-inf,1));
segment.insert(make_pair(inf,-1));
segment.insert(make_pair(inf,1));
int x,y;
int hole = 1;
std::set<pair<int,int> >::iterator itlow,itup;
pf("Case %d:\n",tcase++);
while(Q--){
scanf("%d %d",&x,&y);
assert(1<=x and x<=N);
assert(1<=y and y<=N);
itlow = segment.lower_bound(make_pair(x,-1)) ;
if((*itlow).S==1) itlow--;
itup = segment.upper_bound(make_pair((*itlow).F,-1)) ;
if((*itlow).F==(*itup).F){
segment.erase(itlow);
segment.erase(itup);
if(x!=1 and x!=N)
hole--;
}
else if((*itlow).F==x) {
segment.erase(itlow);
segment.insert(make_pair(x+1,-1 ));
if(x==1 or x==N)
hole++;
}
else if((*itup).F==x) {
segment.erase(itup);
segment.insert(make_pair(x-1,1 ));
if(x==1 or x==N)
hole++;
}
else{
segment.insert(make_pair(x-1,1 ));
segment.insert(make_pair(x+1,-1 ));
hole++;
}
itlow = segment.find(make_pair(y-1,1)) ;
itup = segment.find(make_pair(y+1,-1)) ;
if(itlow!=segment.end() and itup!=segment.end()){
segment.erase(itlow);
segment.erase(itup);
hole--;
}
else if(itlow!=segment.end()){
segment.erase(itlow);
segment.insert(make_pair(y,1));
if(y==1 or y==N)
hole--;
}
else if(itup!=segment.end()){
segment.erase(itup);
segment.insert(make_pair(y,-1));
if(y==1 or y==N)
hole--;
}
else{
segment.insert(make_pair(y,-1));
segment.insert(make_pair(y,1));
if(y!=1 and y!=N)
hole++;
}
pf("%d\n",hole);
}
}
return 0;}
101864G - GCD and LCM of 3 numbers
Setter: codename27 Alternate Writer: Z0RR0, MesbahTanvir
Editorial
Let, x = a/GCD(a,b,c),
y = b/GCD(a,b,c),
z = c/GCD(a,b,c),
[a, b, c are multiple of GCD(a,b,c)]
So, a = x*GCD(a,b,c), b = y*GCD(a,b,c), c = z*GCD(a,b,c)
Then F(a,b,c)
= a*b*c/GCD(a,b,c)
= x*GCD(a,b,c)*y*GCD(a,b,c)*z*GCD(a,b,c)/GCD(a,b,c)
So x*y*z = F(a,b,c)/GCD(a,b,c)^2 = N [Let] …………………………………. (equation 1)
if F(a,b,c) is not a multiple of GCD(a,b,c)^2 then answer is zero.
From equation 1, x*y*z = F(a,b,c)/GCD(a,b,c)^2 = N
x,y,z will be divisors of N and will have GCD(x,y,z) = 1.
Let,
N = p1^e1 p2^e2.....pn^en where p1, p2,..,pn all are unique prime numbers.
Factors of x,y,z will be subset of p1,p2,..pn. At most 2 of x,y,z can have same prime factors because we want GCD(x,y,z) = 1. Now total combination depends on e1,e2,..,en only. From this we can calculate total number of triples possible. But it does not ensure x <= y <= z. We can divide the result by 3!(3 factorial) or 6.Because 3 numbers can permute in 6 ways if the numbers is different. But previous result calculated less for (x,x,z) types triples. So we have to add extra for those combination.
Solution Code
codename27
//#include <bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<complex>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//4-side
//int xx[] = {0,0,-1,1};
//int yy[] = {-1,1,0,0};
//6-side hexagonal
//int xx[] = {2,-2,1,1,-1,-1};
//int yy[] = {0,0,1,-1,1,-1};
#define popc(a) (__builtin_popcount(a))
//ll bigmod(ll a,ll b,ll m){if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a) % m;return x;}
//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M
#define MX 10000100
#define inf 100000000
const double pi = acos(-1.0);
const ll mod = 10000000ll;
const ll mxLim = mod*mod;
ll dp[5][5][200];
ll func(int pos, int zero, int power)
{
if(pos == 3){
if(zero>0 && power == 0) return 1;
return 0;
}
ll &answer = dp[pos][zero][power];
if(answer != -1) return answer;
answer = 0;
for(int i = 0; i <= power; i++)
answer += func(pos+1,zero+(i==0), power-i);
return answer;
}
vector<ll> primes;
int flag[MX];
ll factor(ll n){
if(n == 1) return 1;
//cerr<<">>>"<<n<<"\n";
ll answer = 1;
ll two = 0;
int tem = 0;
for(int i = 0; i < primes.size() && primes[i]*primes[i]<=n; i++){
tem++;
ll cnt = 0;
while(n%primes[i] == 0){
n /= primes[i];
cnt++;
}
if(cnt == 0) continue;
//cerr<<" "<<cnt;
answer *= func(0,0,cnt);
if(cnt%2 == 0){
two++;
}
}
if(n>1){
ll cnt = 1;
answer *= func(0,0,cnt);
if(cnt%2 == 0){
two++;
}
//cerr<<" "<<cnt;
}
//cerr<<"\n";
//cerr<<tem<<"\n";
/*(int i = 0; i < fact.size(); i++){
printf("%lld %lld\n", fact[i].first, fact[i].second);
}*/
//printf("%lld %lld\n", answer, two);
return (answer+3*(1<<two))/6;
}
void calc(){
for(ll i = 2; i < MX; i++){
if(flag[i]) continue;
for(ll j = i+i; j < MX; j += i){
flag[j] = 1;
}
primes.push_back(i);
}
/*printf("%d\n", (int) primes.size());
for(int i = 0; i < 100; i++){
printf("%d %lld\n", i, primes[i]);
}*/
}
int main()
{
//freopen("dataset//sub1in.txt", "r", stdin);
//freopen("input.txt", "r", stdin);
//freopen("dataset//sub1out.txt", "w", stdout);
//freopen("output3.txt", "w", stdout);
memset(dp,-1,sizeof dp);
calc();
int ti;
scanf("%d", &ti);
for(int te = 1; te <= ti; te++){
ll lcm, gcd;
scanf("%lld %lld", &lcm, &gcd);
ll answer = 0;
if(lcm%gcd == 0){
lcm /= gcd;
if(lcm %gcd == 0){
lcm /= gcd;
answer = factor(lcm);
}
}
printf("%lld\n", answer);
}
return 0;
}
Z0RR0
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 10000000
bool pra[N+5];
LL prime[N+5], p;
void sieve()
{
pra[1] = 1;
for(int i = 2; i <= N; i++)
{
if( pra[i] == 0 ) for(int j = i + i; j <= N; j += i) pra[j] = 1;
}
for(int i = 1; i <= N; i++) if( pra[i] == 0 ) prime[p++] = i;
}
vector <int> factorize(LL x)
{
vector <int> ret;
for(int i = 0; i < p; i++)
{
int cnt = 0;
while( x % prime[i] == 0 ) x /= prime[i], cnt++;
if( cnt ) ret.push_back( cnt );
}
if( x > 1 ) ret.push_back( 1 );
return ret;
}
vector <int> global;
int visit[25][2][2][2], dp[25][2][2][2], cs;
int F(int cur, int a, int b, int c)
{
if( cur == global.size() ) return (a + b + c) == 0;
if( visit[cur][a][b][c] == cs ) return dp[cur][a][b][c];
int x = global[cur], ret = 0, item = 1 + ( x % 2 == 0 );
ret += item * F(cur+1,a,0,0);
ret += item * F(cur+1,0,b,0);
ret += item * F(cur+1,0,0,c);
ret += 3 * (x - item) * F(cur+1,0,0,0);
visit[cur][a][b][c] = cs;
return dp[cur][a][b][c] = ret;
}
int solve(LL l, LL g)
{
if( l % g ) return 0;
LL val = l / g;
if( val % g ) return 0;
val /= g;
global = factorize(val);
cs++;
int ret = F(0,1,1,1);
int xtra = 1;
for(int i = 0; i < global.size(); i++) if( global[i] % 2 == 0 ) xtra *= 2;
return ( ret / 6 ) + xtra;
}
int main()
{
//freopen("input04.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
sieve();
LL T, l, g;
scanf("%lld", &T);
assert( 1 <= T && T <= 100 );
for(int t = 1; t <= T; t++)
{
scanf("%lld %lld", &l, &g);
assert( 1 <= l && l <= 1e14 );
assert( 1 <= g && g <= 1e14 );
int ret = solve(l,g);
printf("%d\n", ret);
}
return 0;
}
ISwearItIsMyLastContest
#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define point pair < LL ,LL >
const int N = 10000005;
vector < bool > isp;
vector < int > pr;
#define pb push_back
void Sieve(){
isp.resize(N+5);
pr.reserve(1<<20);
for(int i =0 ; i < N ; i++) isp[0];
int sqr = sqrt(N);
//for(int i=4;i<MAX;i+=2) isp[i]=true;
for(int i=3; i<=sqr; i+=2) if(!isp[i]) for( int j=i*i; j<N ; j+=i<<1) isp[j]=true;
pr.pb(2);
for(int i=3; i<N; i+=2) if(!isp[i]) pr.pb(i);
}
point arr[20]; int n_arr;LL full[20];
LL backTrack(int i,LL p ,LL q ,LL r,LL num){
// breaking condition
// LL rem = (num)/(p;
// if(rem*r<q or rem*q<p) return 0;
if(p * p * p > num or p * q * q > num ) return 0;
if(i == n_arr) return ( p <= q and q <= r);
LL ans =0 , pr = arr[i].first, cnt = arr[i].second;
LL ful = full[i];
ans += backTrack(i + 1, p * ful, q, r, num);
ans += backTrack(i + 1, p, q * ful, r, num);
ans += backTrack(i + 1, p, q, r * ful, num);
if(cnt>1){
for(pr = arr[i].first; pr !=ful; pr *= arr[i].first ){
ans += backTrack(i + 1, p * pr, q * (ful / pr), r, num);
ans += backTrack(i + 1, p, q * pr, r * (ful / pr), num);
ans += backTrack(i + 1, p * pr, q, r * (ful / pr), num);
}
}
return ans;
}
LL solve(LL a){
LL cnt =0 , num=a , element=0;
for(auto i : pr){
for(element=0; a%i==0 ; a/=i) element++;
if(element>=1) arr[cnt++] = {i,element};
}
if(a>1) arr[cnt++] = {a,1};
n_arr = cnt;
for(int i =0 ; i <n_arr ;i++){
LL val = 1;
for(int j =0 ;j <arr[i].second;j++) val*=arr[i].first;
full[i] = val;
}
return backTrack(0 , 1 , 1 , 1 , num);
}
int main(int argc , char *args[]){
// freopen("sub3in.txt","r",stdin);
// freopen("out.txt","w",stdout);
Sieve();
int tc;
scanf("%d",&tc);
while(tc--){
LL a , b;
scanf("%lld %lld",&a,&b);
if(a%b==0 and (a/b)%b==0) printf("%lld\n",solve(a/(b*b)));
else puts("0");
}
return 0;
}
101864H - Little T2 and Derangements
Setter: Z0RR0 Alternate Writer: codename27, flash_7
Editorial
[ Lets Solve when N at most 18 ]
So N can be at most 18 and K can be at most 2e15. For N = 18, we can get more derangements than 2e15. We can write a bitmask DP to generate the number of derangements of N or we can simply use the formula !n = (n-1)[!(n-1)+!(n-2)] where !n denotes the number of derangements for n and !0 = 1 and !1 = 0. Now we can solve the problem with bitmask DP. The state of the DP function is “mask”. This is an N bit number that represents the availability of the numbers. If the i’th bit is 1 then the number i is already put somewhere. If the i’th bit is 0 then we can still put the number i somewhere. By seeing the mask we can know the number of items have been positioned and the current position where we are wanting to put something. The current position is (1 + number of 1 bit of mask). We iterate over all the available numbers(remember, we can not put x in the x’th position) and put the number in current position and call the next state by changing the mask. If we can put every number successfully, this is a derangement of N. This is how we can get the number of derangements of N. But our problem wants the lexicographically K’th derangement of N. This can be found from this DP. In the first position we put the lexicographically smallest available number and check the number of derangements possible further. If this value is less than K then we can reduce our K by this value as these derangements will never be considered and they all are lexicographically smaller than out expected derangement. Now, we try with the next possible smallest available number and check the number of derangements possible further. If this value is less than K we do the same as above. But if this value is equal or greater than K we know we can put this number in this position and all the further derangements are possible with our generated prefix. Now we try the second position same as above. This is how we will get the lexicographically K’th derangement of N. As K will always be valid and you get a derangement at last, the remaining K will be 1.
For each test case the complexity is O(N*2^N).
[Now the actual problem]
N can be at most 100 and K can be at most 2e15. Here is an easy observation. If we are told to generate the K’th permutation, we can easily observe that the change will occur only with a few large numbers. We can use that observation here too. Only last 18/19 numbers are important. Lets call this number of important numbers, M. M can be either 18 or 19 here. We are discussing the solution for N > M.
Lets put the first N-M numbers at their actual position. We know the number of derangements for M is always greater than maximum K. Now what to do with this remaining N-M numbers. Lets say N-M is even. We can take first two numbers and swap them. Then we can take the 3rd and 4th number and swap them. Then we can take the 5th and 6th number and so on. This is how we can get the lexicographically K’th derangement for any N. If N is odd we set M = 19 or if N is even we set M = 18. So, for each test case the complexity is O(M*2^M). But for 1000 test cases this will take so much time. But we only need to calculate for each M once, no matter what is N. So, regardless of T and N the complexity of this solution is O(M*M*2^M).
Solution Code
Z0RR0
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define prntvctr(x) for(int i = 0; i < x.size(); i++) printf("%d%c", x[i], i + 1 == x.size() ? '\n' : ' ' );
#define pc(x) __builtin_popcount(x)
#define D(x) cout << #x << " = " << x << endl
#define DD(x,y) cout << #x << " = " << x << " " << #y << " = " << y << endl
#define DDD(x,y,z) cout << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << endl
int setb(int n,int pos)
{
return n=n | (1 << pos);
}
int resb(int n,int pos)
{
return n=n & ~(1 << pos);
}
bool checkb(int n,int pos)
{
return (bool)(n & (1 << pos));
}
typedef long long LL;
LL drngmnt[25];
void prework()
{
drngmnt[0] = 1;
drngmnt[1] = 0;
for(int i = 2; i <= 20; i++) drngmnt[i] = (i - 1) * ( drngmnt[i-1] + drngmnt[i-2] );
}
void show(vector <int> v)
{
for(int i = 0; i < v.size(); i++)
{
if( i ) printf(" ");
printf("%d", v[i] + 1);
}
puts("");
}
bool visit[20][ (1 << 19) + 5 ];
LL dp[20][ (1 << 19) + 5 ];
LL F(int n, int mask)
{
int pos = pc(mask);
if( pos == n ) return 1;
if( visit[n][mask] ) return dp[n][mask];
LL ret = 0;
for(int i = 0; i < n; i++)
{
if( i == pos ) continue;
if( checkb(mask,i) == 0 ) ret += F( n , setb(mask,i) );
}
visit[n][mask] = 1;
return dp[n][mask] = ret;
}
void solve3(int n, LL k)
{
int need = 0;
for(int i = 1; i <= 20; i++)
{
if( drngmnt[i] >= k )
{
need = i;
break;
}
}
int baki = n - need;
if( baki & 1 ) need++;
vector <int> v;
int mask = 0;
LL rm = k;
for(int i = 0; i < need; i++)
{
LL tot = 0, prv = 0, val;
int here;
for(int j = 0; j < need; j++)
{
if( i == j ) continue;
if( checkb(mask,j) == 0 )
{
LL now = F( need , setb(mask,j) );
tot += now;
if( rm - tot <= 0 )
{
here = j, val = prv;
break;
}
prv = tot;
}
}
rm -= val;
v.push_back( here );
mask = setb( mask , here );
}
assert( rm == 1 );
vector <int> ans;
for(int i = 0; i < n - need; i += 2) ans.push_back( i + 1 ), ans.push_back( i );
for(int i = 0; i < v.size(); i++) ans.push_back( v[i] + n - need );
show( ans );
}
int main()
{
//freopen("input03.txt", "r", stdin);
//freopen("output03.txt", "w", stdout);
prework();
int T, n;
LL k;
scanf("%d", &T);
assert( 1 <= T && T <= 1000 );
for(int t = 1; t <= T; t++)
{
scanf("%d %lld", &n, &k);
assert( 1 <= n && n <= 100 );
assert( 1 <= k && k <= drngmnt[ min(18,n) ] );
assert( 1 <= k && k <= 2e15 );
solve3(n,k);
}
return 0;
}
codename27
//#include <bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<complex>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//4-side
//int xx[] = {0,0,-1,1};
//int yy[] = {-1,1,0,0};
//6-side hexagonal
//int xx[] = {2,-2,1,1,-1,-1};
//int yy[] = {0,0,1,-1,1,-1};
#define popc(a) (__builtin_popcount(a))
//ll bigmod(ll a,ll b,ll m){if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a) % m;return x;}
//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M
#define MX 100005
#define inf 100000000
const double pi = acos(-1.0);
const ll mod = 1000000007ll;
const int Lown = 1;
const int Highn = 1000;
const ll Lowk = 1;
const ll Highk = 2000000000000000ll;
const int mxN = 20;
ll dp[1<<mxN];
ll func(int mask){
if(mask+1 == (1<<mxN)) return 1;
ll & res = dp[mask];
if(res != -1) return res;
res = 0;
int now = __builtin_popcount(mask);
for(int i = 0; i < mxN; i++){
if(i == now || ((mask>>i)&1)) continue;
res += func(mask|(1<<i));
}
return res;
}
vector<int> result;
void func(int n, ll k){
result.clear();
int mask = 0;
for(int i = 0; i < (mxN-n); i++)
mask |= (1<<i);
for(int i = mxN-n; i < mxN; i++){
for(int j = 0; j < mxN; j++){
if(i == j || ((mask>>j)&1)) continue;
ll tem = func(mask|(1<<j));
if(tem>=k){
result.push_back(j+1);
mask |= (1<<j);
break;
}else{
k -= tem;
}
}
}
for(int i = 0; i < n; i++){
result[i] -= mxN-n;
}
}
//ll ch[100];
vector<int> answer;
void calc(int n, ll k){
answer.clear();
for(int i = 1; n-i >= mxN; i+=2){
answer.push_back(i+1);
answer.push_back(i);
}
int baki = n-answer.size();
func(baki,k);
//printf("ok %d\n", baki);
for(int i = 0; i < baki; i++){
answer.push_back(result[i]+n-baki);
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("subtask 3//input03.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//freopen("subtask 3//my3output03.txt", "w", stdout);
/*ch[0] = 1;
ch[1] = 0;
for(int i = 2; i < 20; i++){
ch[i] = (i-1)*(ch[i-1]+ch[i-2]);
printf("%d %lld\n", i, ch[i]);
}
return 0;*/
memset(dp,-1,sizeof dp);
int ti, n;
ll k;
scanf("%d", &ti);
for(int te = 1; te <= ti; te++){
cerr<<te<<endl;
scanf("%d %lld", &n, &k);
assert(Lown<=n && n <= Highn);
assert(Lowk<=k && k <= Highk);
calc(n,k);
//continue;
for(int i = 0; i < n; i++){
printf("%d%c", answer[i], (i == n-1)? '\n':' ');
}
}
return 0;
}
flash_7
///====================== TEMPLATE STARTS HERE =====================///
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp> // Include for built in treap
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#include <sys/resource.h> // for linux stack memory increase
//#define gc getchar_unlocked // for linux fast io
//#define gc getchar // for windows fast io
#define pb push_back
#define MP make_pair
#define ff first
#define ss second
#define nl puts("")
#define sp printf(" ")
#define phl debug("Hello")
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((vlong)(x).size())
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define SQ(x) ((x)*(x))
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define ODD(x) (((x)&1)==0?(0):(1))
#define Set(N,p) N=((N)|((1LL)<<(p)))
#define Reset(N,p) N=((N)&(~((1LL)<<(p))))
#define Check(N,p) (!(((N)&((1LL)<<(p)))==(0)))
#define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
#define arrayIndexPrint(A,i) cerr<<"~ At pos: "<<i<<" = "<<A[i]
#define dump(x) cerr<<"~ "<<#x<<" = "<<x<<endl
#define arrayPrint(A,st,ed) cerr<<"~ Array:";FOR(i,st,ed) cerr<<" "<<A[i];cerr<<endl
#define LINE cerr<<"\n"; FOR(i,0,50) cerr<<"=";cerr<<"\n\n"
#define LL long long
#define LLU long long unsigned int
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<int> vi;
typedef vector<vlong> vl;
typedef vector<pll> vll;
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pb_ds;
#ifdef forthright48
#include <ctime>
clock_t tStart = clock();
#define debug(args...) {dbg,args; cerr<<endl;}
#define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#define bug printf("%d\n",__LINE__);
#else
#define debug(args...) // Just strip off all debug tokens
#define timeStamp
#endif
struct debugger{
template<typename T> debugger& operator , (const T& v){
cerr<<v<<" ";
return *this;
}
}dbg;
inline vlong gcd ( vlong a, vlong b ) {
a = ABS ( a ); b = ABS ( b );
while ( b ) { a = a % b; swap ( a, b ); } return a;
}
vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
x2 = 1; y2 = 0;
x1 = 0; y1 = 1;
for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
q = r2 / r1;
r = r2 % r1;
x = x2 - (q * x1);
y = y2 - (q * y1);
}
*X = x2; *Y = y2;
return r2;
}
inline vlong modInv ( vlong a, vlong m ) {
vlong x, y;
ext_gcd( a, m, &x, &y );
x %= m;
if ( x < 0 ) x += m;
return x;
}
inline vlong bigmod ( vlong a, vlong p, vlong m ) {
vlong res = 1 % m, x = a % m;
while ( p ) {
if ( p & 1 ) res = ( res * x ) % m;
x = ( x * x ) % m; p >>= 1; /// For bigmod2 multiply here using mulmod
}
return res;
}
//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
//int dir8[8][2] = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{1,1},{1,-1},{-1,1}};
const vlong inf = 2147383647;
const vlong mod = 1000000007;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-11;
///====================== TEMPLATE ENDS HERE =====================///
const int MX = 19;
LL DP[(1<<MX)+10][MX];
/// DP[m][k] = Number of derangements possible
/// m = mask of selected items, k = remaining positions
vector<int> res;
int SN;
LL call(int cur, int mask){
if(cur == SN){
return DP[mask][SN-cur] = 1;
}
if(DP[mask][SN-cur] != -1) return DP[mask][SN-cur];
LL sum = 0;
FOR(p,0,SN-1){
if(p == cur || Check(mask, p)) continue;
int nmask = mask;
Set(nmask, p);
sum += call(cur+1, nmask);
}
return DP[mask][SN-cur] = sum;
}
void store(int cur, int mask, LL rem, int pfx){
if(cur == SN) return;
LL sum = 0;
FOR(p,0,SN-1){
if(p == cur || Check(mask, p)) continue;
int nmask = mask;
Set(nmask, p);
LL add = DP[nmask][SN-cur-1];
if(sum+add >= rem){
res.pb(p+pfx);
store(cur+1, nmask, rem-sum, pfx);
return;
}
sum += add;
}
}
void solve(LL N, LL K){
res.clear();
if(N<=19){
SN = N;
call(0, 0);
store(0, 0, K, 0);
}else{
if(N%2 == 0) SN = 18;
else SN = 19;
int FPP = N - SN; /// Greedy choice for first FPP items
for(int i = 0;i<FPP;i+=2){
res.pb(i+1);
res.pb(i);
}
call(0, 0);
store(0, 0, K, FPP);
}
}
int main () {
#ifdef forthright48
//freopen ( "input.txt", "r", stdin );
//freopen ( "output.txt", "w", stdout );
#endif // forthright48
int t;
scanf("%d",&t);
assert(t>=1 && t<=1000);
CLR(DP, -1);
FOR(cs,1,t){
LL N, K;
scanf("%lld %lld",&N,&K);
assert(N>=2 && N<=100);
assert(K>=1 && N<=2000000000000000LL);
solve(N, K);
FOR(i,0,N-1){
if(i!=0) printf(" ");
printf("%d",res[i]+1);
}
printf("\n");
}
return 0;
}
Setter: Alpha_Q Alternate Writer: bertho_coder
Editorial
Tag — Mathematics, Observation
Let me throw away the solution first, then we’ll get to the explanation. Let S be the sum of all pile sizes, and G be the greatest common divisor (GCD) of all pile sizes. We claim that the task is possible if and only if S/G is a perfect power of 2.
The trick is to look at the process backwards. The move is (a,b) --> (a-b, 2b). Let’s define x = a — b and y = 2b, then: b = y/2 and a = x + y/2. So the reverse (undo) move is (x, y) --> (x + y/2, y/2).
Notice: this just means that we can take half of the marbles from a pile and add them to another. We can only take marbles from piles having even sizes.
Suppose S = (2^t) * M where M is odd. Then it is clear that the transfer amount of any reverse move is a multiple of M. Therefore, the GCD of all pile sizes (after a finite number of moves) is a multiple of M as well. Dividing S by G cancels out the M and leaves us with a power of 2. So S/G being a power of 2 is necessary for the task to be possible.
Now we prove that it is sufficient as well. We’ll use a crucial fact about the process here: the process is invariant up to scaling by a factor. Indeed, we can see that (ka, kb) --> (ka — kb, 2kb) is just k(a, b) --> k(a — b, 2b).
So without loss of generality, we let M = 1 and induct on t (so S = 2^t is the sum of all pile sizes). The case t = 0 is trivial: since S = 1 means there’s only one pile of size 1. Now we consider t > 0. Since the sum S = 2 ^ t is even, the number of piles having odd-numbered sizes must be even (why?). So now we can pair those piles up and spend a move per pair to turn both sizes even. This is because (2x + 1, 2y + 1) --> ( 2 (x -y), 2 (2y + 1)), both of which are even. Now that all of the piles have even sizes, we can divide each pile size by 2 (remember that the process is invariant up to scaling), and the problem reduces to an instance of pile sizes with sum ** 2*(t-1)**. This instance is solvable by our induction hypothesis. So the claim is proved by induction.
Hence our claim is both necessary and sufficient. If the task is not possible, we can just keep adding marbles to a pile till S becomes a power of 2, so changing a single pile is always sufficient.
Complexity (per test): O(n lg( max(Ai) ))
Solution Code
Alpha_Q
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic warning "-std=c++11"
// O(n lg(max A)) per test.
// Necessary and sufficient condition: sum / gcd = 2^t for some t >= 0.
// For bad case: just adjust one pile to meet the above condition.
int t, cs, n;
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
long long sum = 0;
long long gcd = 0;
for (int i = 0; i < n; ++i) {
long long x;
scanf("%lld", &x);
sum += x;
gcd = __gcd(x, gcd);
}
printf("Case %d: ", ++cs);
if (__builtin_popcountll(sum / gcd) == 1) puts("YES");
else puts("NO 1");
}
return 0;
}
101864J - Non Super Boring Substring
Setter: flash_7 Alternate Writer: prophet_ov_darkness, aminul
Editorial
Tag: Manacher, Hashing, Two Pointer
Let’s consider a super-boring substring(u, v) which contains a palindromic substring of length z. Now if z > k+1, then the super boring substring(u, v) must also contain another palindromic substring of length k or k+1. So we only need to consider those palindromic substring whose length is either k or k+1.
Now let's apply manacher. For each position u in the string s, manacher finds the length of the largest palindrome whose center is u.
Using this information we can build an array MXP where: MXP[u] = k, if substring(u, u+k) is a palindrome,
or MXP[u] = k+1, if substring(u, u+k+1) is palindrome, otherwise MXP[u] = -1.
Now we iterate from right to the left and use the 2 pointer technique. The 1st pointer is v, which means that we consider the index v as the ending position of a non super-boring substring. The 2nd pointer is u, which means that u is the smallest position such that substring(u, v) doesn’t contain any palindromic substring of length k or k + 1. We can move this two pointers to the left(when necessary) using the information from the MXP array and keep track of the result of how many non super-boring substring are there which ends at position v. Overall Complexity: O(N)****.
Solution Code
flash_7
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
#define ff first
#define ss second
#define nl puts("")
#define sp printf(" ")
#define phl debug("Hello")
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((vlong)(x).size())
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define SQ(x) ((x)*(x))
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define ODD(x) (((x)&1)==0?(0):(1))
#define Set(N,p) N=((N)|((1LL)<<(p)))
#define Reset(N,p) N=((N)&(~((1LL)<<(p))))
#define Check(N,p) (!(((N)&((1LL)<<(p)))==(0)))
#define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
#define arrayIndexPrint(A,i) cerr<<"~ At pos: "<<i<<" = "<<A[i]
#define dump(x) cerr<<"~ "<<#x<<" = "<<x<<endl
#define arrayPrint(A,st,ed) cerr<<"~ Array:";FOR(i,st,ed) cerr<<" "<<A[i];cerr<<endl
#define LINE cerr<<"\n"; FOR(i,0,50) cerr<<"=";cerr<<"\n\n"
#define LL long long
#define LLU long long unsigned int
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<int> vi;
typedef vector<vlong> vl;
typedef vector<pll> vll;
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pb_ds;
#ifdef forthright48
#include <ctime>
clock_t tStart = clock();
#define debug(args...) {dbg,args; cerr<<endl;}
#define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#define bug printf("%d\n",__LINE__);
#else
#define debug(args...) // Just strip off all debug tokens
#define timeStamp
#endif
struct debugger{
template<typename T> debugger& operator , (const T& v){
cerr<<v<<" ";
return *this;
}
}dbg;
inline vlong gcd ( vlong a, vlong b ) {
a = ABS ( a ); b = ABS ( b );
while ( b ) { a = a % b; swap ( a, b ); } return a;
}
vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
x2 = 1; y2 = 0;
x1 = 0; y1 = 1;
for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
q = r2 / r1;
r = r2 % r1;
x = x2 — (q * x1);
y = y2 — (q * y1);
}
*X = x2; *Y = y2;
return r2;
}
inline vlong modInv ( vlong a, vlong m ) {
vlong x, y;
ext_gcd( a, m, &x, &y );
x %= m;
if ( x < 0 ) x += m;
return x;
}
inline vlong bigmod ( vlong a, vlong p, vlong m ) {
vlong res = 1 % m, x = a % m;
while ( p ) {
if ( p & 1 ) res = ( res * x ) % m;
x = ( x * x ) % m; p >>= 1; /// For bigmod2 multiply here using mulmod
}
return res;
}
//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
//int dir8[8][2] = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{1,1},{1,-1},{-1,1}};
const vlong inf = 21473836470LL;
const vlong mod = 1000000007;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-11;
const int Size = 100055;
///====================== TEMPLATE ENDS HERE =====================///
#define MANALEN 200100
struct MANACHER {
char arr[MANALEN+10], brr[MANALEN+10];
int p[MANALEN+10];
int an, bn, mxpalin, mxcenter;
void init() {
an = strlen ( arr );
}
void preprocess() {
int cur = 0;
brr[cur++] = '^';
FOR(i,0,an-1) {
brr[cur++] = '#';
brr[cur++] = arr[i];
}
brr[cur++] = '#';
brr[cur++] = '$';
brr[cur] = 0;
bn = cur;
}
void calc() {
int c = 0, r = 0;
FOR(i,1,bn-2) {
int mi = c - (i-c);
p[i] = (r > i )? MIN ( r - i, p[mi] ): 0;
while ( brr[i+p[i]+1] == brr[i-p[i]-1] ) {
p[i]++;
}
if ( i + p[i] > r ) {
r = i + p[i];
c = i;
}
}
mxpalin = 0; mxcenter = 0;
FOR(i,1,bn-2) {
if ( p[i] > mxpalin ) {
mxpalin = p[i];
mxcenter = i;
}
}
}
}mana;
int N, K;
char s[Size];
bool ispalin[Size][2];
LL stpos[Size];
void precalc(){
strcpy(mana.arr, s);
mana.init();
mana.preprocess();
mana.calc();
FOR(i, 2, mana.bn-1){
if(i%2 == 0){ /// Odd
int len = mana.p[i];
int mid = (i-1)/2;
int st = mid - len/2;
int xk = K;
if(K%2 == 0) xk++;
if(xk>len) continue;
int ext = (len - xk)/2;
st += ext;
if(K == xk) ispalin[st][0] = 1;
else ispalin[st][1] = 1;
}else{ /// Even
int len = mana.p[i];
int mid = (i-1-1)/2;
int st = mid - len/2 + 1;
int xk = K;
if(K%2 == 1) xk++;
if(xk>len) continue;
int ext = (len - xk)/2;
st += ext;
if(K == xk) ispalin[st][0] = 1;
else ispalin[st][1] = 1;
}
}
}
LL solve(){
CLR(ispalin, 0);
precalc();
CLR(stpos, -1);
FOR(st,0,N-1){
if(ispalin[st][0] == 1){
int ed = st+K-1;
stpos[ed] = max(stpos[ed], st);
}
if(ispalin[st][1] == 1){
int ed = st+K+1-1;
stpos[ed] = max(stpos[ed], st);
}
}
LL res = 0;
int st = 0, ed = 0;
while(st<N){
while(ed<N && stpos[ed]<st) ed++;
res += (ed - st);
st++;
}
return res;
}
int main() {
#ifdef forthright48
freopen ( "input01.txt", "r", stdin );
//freopen ( "output01.txt", "w", stdout );
#endif // forthright48
int t;
scanf("%d",&t);
assert(t>=1 && t<=100);
LL sum = 0;
FOR(cs,1,t){
scanf("%d %s",&K,s);
N = strlen(s);
sum += N;
assert(K>=1 && K<=N);
assert(N>=1 && N<=100000);
FOR(i,0,N-1){
assert(s[i]>='a' && s[i]<='z');
}
LL res = solve();
printf("%lld\n",res);
}
assert(sum>=1 && sum<=1000000);
}
prophet_ov_darkness
#include <bits/stdc++.h>
using namespace std;
#define DB(x) cerr << #x << " = " << x << endl
#define OK cerr << "ok\n"
typedef long long LL;
const int MAX = 100005;
int n, k, limit[MAX];
char str[MAX];
/*** Manacher's algorithm to generate longest palindromic substrings for all centers ***/
/// When i is even, pal[i] = largest palindromic substring centered from str[i / 2]
/// When i is odd, pal[i] = largest palindromic substring centered between str[i / 2] and str[i / 2] + 1
vector <int> manacher(char *str){
int i, j, k, l = strlen(str), n = l << 1;
vector <int> pal(n);
for (i = 0, j = 0, k = 0; i < n; j = max(0, j - k), i += k){
while (j <= i && (i + j + 1) < n && str[(i - j) >> 1] == str[(i + j + 1) >> 1]) j++;
for (k = 1, pal[i] = j; k <= i && k <= pal[i] && (pal[i] - k) != pal[i - k]; k++){
pal[i + k] = min(pal[i - k], pal[i] - k);
}
}
pal.pop_back();
return pal;
}
inline LL solve() {
vector <int> v = manacher(str);
int i, siz = (int)v.size();
LL ret = 0;
for(i=0; i<n; i++) limit[i] = n-1;
for(i=0; i<siz; i++) {
if(v[i] >= k) {
if(i%2 == 0) {
int now = k/2;
int addr = i/2;
limit[addr-now] = min(limit[addr-now], addr+now-1);
}
else {
int now = (k+1)/2;
int addr = i/2;
limit[addr-now+1] = min(limit[addr-now+1], addr+now-1);
}
}
}
int now = n-1;
for(i=n-1; i>=0; i--) {
now = min(now, limit[i]);
limit[i] = now;
}
for(i=0; i<n; i++) {
ret += max(0ll, (LL)limit[i]-(LL)i+1ll);
}
return ret;
}
int main() {
// assert(freopen("input03.txt", "r", stdin));
// assert(freopen("out.txt", "w", stdout));
clock_t st = clock();
int test, totLen=0;
assert(scanf("%d", &test) == 1);
assert(1 <= test && test <= 100);
while(test--) {
assert(scanf("%d", &k) == 1);
assert(scanf("%s", str) == 1);
n = strlen(str);
assert(1 <= n && n <= 100000);
assert(k <= n);
totLen += n;
printf("%lld\n", solve());
}
assert(totLen <= 1000000);
clock_t en = clock();
fprintf(stderr, "%.3f sec\n", (double)(en-st) / (double)CLOCKS_PER_SEC);
return 0;
}
aminul
/**
* Created by Aminul on 6/30/2018.
*/
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class NonSuperBoringSubstring_ST_2_3_slow {
public static void main(String[] args) throws Exception {
new Thread(null ,new Runnable(){
public void run(){try{solveIt();} catch(Exception e){e.printStackTrace();}}
},"Main",1<<25).start();
}
public static void solveIt() throws Exception {
InputReader in = new InputReader(System.in);
PrintWriter pw = new PrintWriter(System.out);
int test = in.nextInt();
for(int t = 1; t <= test; t++) {
int k = in.nextInt();
char [] s = in.next().toCharArray();
int n = s.length;
Hashing hash = new Hashing(s);
reverseArray(s);
Hashing reverseHash = new Hashing(s);
TreeSet<Integer> even = new TreeSet<>(), odd = new TreeSet<>();
for(int i = 0; i < n; i++){
int j = i + k - 1;
if(j >= n) break;
if(hash.getHash(i, j) == reverseHash.revHash(i, j)){
even.add(j);
}
}
for(int i = 0; i < n; i++){
int j = i + k;
if(j >= n) break;
if(hash.getHash(i, j) == reverseHash.revHash(i, j)){
odd.add(j);
}
}
long boringSubstrings = 0;
for(int i = 0; i < n; i++){
Integer next1 = even.ceiling(i+k-1), next2 = odd.ceiling(i+k);
Integer next = getSmallerNext(next1, next2);
if(next == null) continue;
boringSubstrings += (n - next);
}
long totalSubstrings = (n * (n + 1L)) / 2L;
long nonBoringSubstrings = totalSubstrings - boringSubstrings;
pw.println(nonBoringSubstrings);
}
pw.close();
}
static Integer getSmallerNext(Integer a, Integer b){
if(a == null && b == null) return null;
if(a == null) return b;
if(b == null) return a;
return min(a, b);
}
static void reverseArray(char a[]){
for(int i = 0, j = a.length-1; i < j; i++, j--){
char temp = a[i]; a[i] = a[j]; a[j] = temp;
}
}
static class Hashing{
long[] hash1, hash2;
long[] inv1, inv2;
int n;
long mod1 = 1000000097L;
long mod2 = (long) 1e9 + 9;
long multiplier1 = 43, multiplier2 = 31;
long invMultiplier1 = 441860508;
long invMultiplier2 = 838709685;
Hashing(char[] s) {
build_Hash(s);
}
void build_Hash(char[] s) {
n = s.length;
hash1 = new long[n + 1];
hash2 = new long[n + 1];
inv1 = new long[n + 1];
inv2 = new long[n + 1];
inv1[0] = 1;
inv2[0] = 1;
long p1 = 1;
long p2 = 1;
for (int i = 0; i < n; i++) {
hash1[i + 1] = (hash1[i] + s[i] * p1) % mod1;
p1 = (p1 * multiplier1) % mod1;
inv1[i + 1] = inv1[i] * invMultiplier1 % mod1;
hash2[i + 1] = (hash2[i] + s[i] * p2) % mod2;
p2 = (p2 * multiplier2) % mod2;
inv2[i + 1] = inv2[i] * invMultiplier2 % mod2;
}
}
long getHash(int i, int j) { //0-based
return getHash_2(i, j - i+1);
}
long getHash_2(int i, int len) { //i is 0 based indexed
return (((hash1[i + len] - hash1[i] + mod1) * inv1[i] % mod1) << 32)
+ (hash2[i + len] - hash2[i] + mod2) * inv2[i] % mod2;
}
long revHash(int i, int j){ ////0-based
return getHash(n-j-1, n-i-1);
}
}
static void debug(Object...obj) {
System.err.println(Arrays.deepToString(obj));
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
//InputReader in = new InputReader(new FileReader("File_Name"));
public InputReader(FileReader file) {
reader = new BufferedReader(file);
tokenizer = null;
}
public String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens())
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
return null;
}
return tokenizer.nextToken();
}
public String nextLine() {
String line = null;
try {
tokenizer = null;
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public int nextInt() {
return Integer.parseInt(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public boolean hasNext(){
try {
while (tokenizer == null || !tokenizer.hasMoreTokens())
tokenizer = new StringTokenizer(reader.readLine());
}
catch (Exception e) {
return false;
}
return true;
}
}
}
Setter: aminul Alternate Writer: Z0RR0
Editorial
Let's think of an easier version of this problem, where Y will be always non-negative. How to solve that? The trick here is, the order of values won’t change after each update. So first sort the array. Now if you subtract Y from smaller values or add Y to larger values, the array will still be sorted, their order won’t change. So this can be solved easily with Segment Tree lazy propagation in O(Q*log(n)).
Now, to solve this problem (both for negative and non-negative Y) we need a treap(with lazy propagation). First insert all the numbers into a treap. Now, for updates with non-negative Y, simply do range update on treap. And for negative Y, remove those numbers (less/equal or greater/equal to X) from treap, and re-insert them after adding/subtracting with Y. At most N numbers will be removed and re-inserted in the treap for negative Y. This can also be done in O(Q*log(n)).
Solution Code
aminul
/**
* Created by Aminul on 6/29/2018.
*/
import java.io.*;
import java.util.Arrays;
import java.util.InputMismatchException;
public class RayRayArray_ST_03_FINAL {
public static void main(String[] args) throws Exception {
new Thread(null ,new Runnable(){
public void run(){try{solveIt();} catch(Exception e){e.printStackTrace();}}
},"Main",1<<25).start();
}
public static void solveIt() throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter pw = new PrintWriter(System.out);
int test = in.nextInt();
for(int t = 1; t <= test; t++) {
MyTreap_With_Range_Update treap = new MyTreap_With_Range_Update();
int n = in.nextInt(), q = in.nextInt();
for (int i = 0; i < n; i++) {
int x = in.nextInt();
treap.insert(x, i);
}
for (int i = 0; i < q; i++) {
int tp = in.nextInt();
long x = in.nextLong(), y = in.nextLong();
treap.doUpdate(tp, x, y);
}
long arr[] = treap.getFinalArray(new long[n]);
for (int i = 0; i < n; i++) {
pw.print(arr[i]);
if (i < n - 1) pw.print(" ");
}
pw.println();
}
pw.close();
}
static class MyTreap_With_Range_Update { // Add X to a range of nodes/values
static class Node {
long key, lazy;
int index;
double priority;
Node left,right;
int size;
Node(long key, int idx) {
this.key = key;
this.index = idx;
priority = Math.random();
size = 1;
}
void update() {
size = 1 + getSize(left) + getSize(right);
}
int getSize(Node root) {
return root == null ? 0 : root.size;
}
}
void doUpdate(int type, long x, long y){
if(y == 0) return;
if(y > 0) solveForNonNegative(type, x, y);
else solveForNegative(type, x, y);
}
void solveForNonNegative(int type, long x, long y){
if( type == 1){
splitRecursive(root, x);
lazy_update(splitL, -y);
root = merge(splitL, splitR);
}
else{
splitRecursive(root, x-1);
lazy_update(splitR, y);
root = merge(splitL, splitR);
}
}
void solveForNegative(int type, long x, long y){
if(type == 1){
splitRecursive(root, x);
Node tmp = splitL;
root = splitR;
lazy_update(tmp, -y);
solveForNegative(tmp);
}
else{
splitRecursive(root, x-1);
Node tmp = splitR;
root = splitL;
lazy_update(tmp, y);
solveForNegative(tmp);
}
}
void solveForNegative(Node node){
if(node == null) return;
pushDown(node);
root = insert(root, node.key, node.index);
solveForNegative(node.left);
solveForNegative(node.right);
}
long arr[];
long[] getFinalArray(long[] a){
arr = a;
getFinalArray(root);
return arr;
}
void getFinalArray(Node node){
if(node == null) return;
pushDown(node);
arr[node.index] = node.key;
getFinalArray(node.left);
getFinalArray(node.right);
}
Node root;
void insert(long k, int idx){
root = insert(root, k, idx);
}
void remove(int k){
root = remove(root, k);
}
long getKth(int k){
return kth(root, k);
}
int getSize(Node root) {
return root == null ? 0 : root.size;
}
int size(){
return getSize(root);
}
int orderOf(int k){ // number of elements < k
return orderOf(root, k);
}
int orderOf(Node temp, int k){ // number of elements < k
int x = 0;
if(temp == null) return 0;
if(temp.key < k) return getSize(temp.left) + 1 + orderOf(temp.right, k);
else return orderOf(temp.left, k);
}
Node splitL, splitR;
void splitRecursive(Node t, long x){
if(t == null){
splitL = null;
splitR = null;
return;
}
pushDown(t);
if(t.key <= x){
splitRecursive(t.right, x);
t.right = splitL;
splitL = t;
}
else{
splitRecursive(t.left, x);
t.left = splitR;
splitR = t;
}
t.update();
}
void lazy_update(Node root, long x){
if(root != null){
root.key += x;
root.lazy += x;
}
}
void pushDown(Node root){
if(root == null || root.lazy == 0) return;
if(root.left != null){
root.left.key += root.lazy;
root.left.lazy += root.lazy;
}
if(root.right != null){
root.right.key += root.lazy;
root.right.lazy += root.lazy;
}
root.lazy = 0;
}
Node merge(Node left, Node right) {
pushDown(left); pushDown(right);
if (left == null)
return right;
if (right == null)
return left;
if (left.priority > right.priority) {
left.right = merge(left.right, right);
left.update();
return left;
} else {
right.left = merge(left, right.left);
right.update();
return right;
}
}
Node insert(Node root, long x, int idx) {
splitRecursive(root, x);
return merge(merge(splitL, new Node(x, idx)), splitR);
}
Node remove(Node root, int x) {
if (root == null) {
return null;
}
if (x < root.key) {
root.left = remove(root.left, x);
root.update();
return root;
} else if (x > root.key) {
root.right = remove(root.right, x);
root.update();
return root;
} else {
return merge(root.left, root.right);
}
}
long kth(Node n, int k) {
if (n == null) return -1;
int key = getSize(n.left) + 1;
if (key > k) return kth(n.left, k);
else if (key < k) return kth(n.right, k - key);
return n.key;
}
void print(){
print(root);
System.err.println();
}
void print(Node root) {
pushDown(root);
if (root == null)
return;
print(root.left);
System.err.print(root.key+","+root.index+"; " );
print(root.right);
}
}
static void debug(Object...obj) {
System.err.println(Arrays.deepToString(obj));
}
static class FastReader {
InputStream is;
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
static final int ints[] = new int[128];
public FastReader(InputStream is){
for(int i='0';i<='9';i++) ints[i]=i-'0';
this.is = is;
}
public int readByte(){
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
public boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
public int skip() {
int b;
while((b = readByte()) != -1 && isSpaceChar(b));
return b;
}
public String next(){
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public int nextInt(){
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = (num<<3) + (num<<1) + ints[b];
}else{
return minus ? -num : num;
}
b = readByte();
}
}
public long nextLong() {
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = (num<<3) + (num<<1) + ints[b];
}else{
return minus ? -num : num;
}
b = readByte();
}
}
public double nextDouble() {
return Double.parseDouble(next());
}
/* public char nextChar() {
return (char)skip();
}*/
public char[] next(int n){
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
/*private char buff[] = new char[1005];
public char[] nextCharArray(){
int b = skip(), p = 0;
while(!(isSpaceChar(b))){
buff[p++] = (char)b;
b = readByte();
}
return Arrays.copyOf(buff, p);
}*/
}
}
Z0RR0
#include <bits/stdc++.h>
//#include <unordered_map>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define rep(i,n) for(i=1;i<=n;i++)
#define Rep(i,n) for(i=0;i<n;i++)
#define For(i,a,b) for(i=a;i<=b;i++)
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mem(ara,val) memset(ara,val,sizeof(ara))
#define eps 1e-7
#define si(x) scanf("%d",&x)
#define sii(x,y) scanf("%d %d",&x,&y)
#define siii(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sll(x,y) scanf("%lld %lld",&x,&y)
#define slll(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define ss(str) scanf("%s",str)
#define pi(x) printf("%d",x)
//#define pii(x,y) printf("%d %d",x,y)
#define piii(x,y,z) printf("%d %d %d",x,y,z)
#define pl(x) printf("%lld",x)
#define pll(x,y) printf("%lld %lld",x,y)
#define plll(x,y,z) printf("%lld %lld %lld",x,y,z)
#define NL printf("\n")
#define Max 1000005
#define INF 1e18
#define un(x) x.erase(unique( x.begin() , x.end() ), x.end())
#define mod 1000000007
#define FI freopen("z.txt","r",stdin)
#define D(x) cout << #x << " = " << x << endl
#define DD(x,y) cout << #x << " = " << x << " " << #y << " = " << y << endl
#define DDD(x,y,z) cout << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << endl
#define all(x) x.begin(),x.end()
#define prntvctr(x) for(int i = 0; i < x.size(); i++) printf("%d%c", x[i], i + 1 == x.size() ? '\n' : ' ' );
#define pc(x) __builtin_popcount(x)
#define inside(a,b,c) assert( a <= b && b <= c )
typedef long long LL;
typedef unsigned long long ULL;
const double PI = acos(-1.0);
using namespace std;
int setb(int n,int pos)
{
return n=n | (1 << pos);
}
int resb(int n,int pos)
{
return n=n & ~(1 << pos);
}
bool checkb(LL n,LL pos)
{
return (bool)(n & (1ll << pos));
}
LL bigmod(LL b,LL p,LL m)
{
if( p == 0 ) return 1;
LL ret = bigmod(b,p/2,m);
ret = ( ret * ret ) % m;
if( p & 1 ) ret = ( ret * b ) % m;
return ret;
}
struct node
{
int prior, size;
LL val; ///value stored in the array
LL sum; ///whatever info you want to maintain in segtree for each node
LL lazy; ///whatever lazy update you want to do
int idx;
struct node *l,*r;
};
typedef node* pnode;
int SZ(pnode t)
{
return t ? t->size : 0;
}
void upd_sz(pnode t)
{
if(t) t->size = SZ(t->l) + SZ(t->r) + 1;
}
void lazy(pnode t)
{
if( !t || !t->lazy ) return;
t->val += t->lazy; ///operation of lazy
t->sum += t->lazy * SZ(t);
if(t->l) t->l->lazy += t->lazy; ///propagate lazy
if(t->r) t->r->lazy += t->lazy;
t->lazy = 0;
}
void reset(pnode t)
{
if(t) t->sum = t->val; /**no need to reset lazy coz when we call this lazy would itself be propagated**/
}
void combine(pnode &t, pnode l, pnode r)
{
///combining two ranges of segtree
if(!l || !r) return void (t = l ? l : r); ///why do you do this????
t->sum = l->sum + r->sum;
}
void operation(pnode t)
{
///operation of segtree
if(!t) return;
reset(t); ///reset the value of current node assuming it now represents a single element of the array
lazy(t->l);
lazy(t->r);///imp:propagate lazy before combining t->l,t->r;
combine(t,t->l,t);
combine(t,t,t->r);
}
void Split(pnode t, pnode &l, pnode &r, int pos, int add = 0)
{
if(!t) return void(l = r = NULL);
lazy(t);
int curr_pos = add + SZ(t->l) + 1;
if(curr_pos <= pos) Split(t->r, t->r, r, pos, curr_pos),l = t;///element at pos goes to left subtree(l)
else Split(t->l, l, t->l, pos, add), r = t;
upd_sz(t);
operation(t);
}
void Merge(pnode &t,pnode l,pnode r)
{
///l->leftarray,r->rightarray,t->resulting array
lazy(l);
lazy(r);
if(!l || !r) t = l ? l : r;
else if(l->prior > r->prior) Merge(l->r,l->r,r), t = l;
else Merge(r->l,l,r->l), t = r;
upd_sz(t);
operation(t);
}
pnode init(LL val, int idx)
{
pnode ret = new node();
ret->prior = rand(); ///if linux
//ret->prior = rand() * rand(); ///if windows
ret->size = 1;
ret->val = val;
ret->idx = idx;
ret->sum = val;
ret->lazy = 0;
return ret;
}
void ArrayInsert(pnode &t, pnode it, int pos)
{
pos++;
pnode L, R, tmp;
Split(t, L, R, pos - 1);
Merge(L, L, it);
Merge(t, L, R);
}
void ArrayDelete(pnode &t, int pos)
{
pos++;
pnode L, R, tmp;
Split(t, L, R, pos);
Split(L, L, tmp, pos-1);
delete(tmp);
Merge(t, L, R);
}
int keep;
LL ArrayValue(pnode &t, int pos)
{
pos++;
pnode L, mid, R;
Split(t,L,mid,pos-1);
Split(mid,t,R,1);
LL ans = t->val;
keep = t->idx;
Merge(mid,L,t);
Merge(t,mid,R);
return ans;
}
void order_of_key(pnode &t, LL x, int car, int &ans)
{
lazy(t);
if( t->val <= x )
{
int xtra = 0;
if( t->l ) xtra = t->l->size;
ans = max( ans , xtra + car );
if( t->r ) order_of_key(t->r, x, car + 1 + xtra, ans);
}
else if( t->l ) order_of_key(t->l, x, car, ans);
}
void Clear(pnode &root)
{
while( root->size > 1 ) ArrayDelete( root, root->size - 1 );
}
LL query(pnode &t,int l,int r)
{
l++;
r++;
///[l,r]
pnode L, mid, R;
Split(t,L,mid,l-1);
Split(mid,t,R,r-l+1);///note: r-l!!
int ans = t->sum;
Merge(mid,L,t);
Merge(t,mid,R);
return ans;
}
void update(pnode &t, int l, int r, LL val)
{
l++;
r++;
///[l,r]
pnode L,mid,R;
Split(t,L,mid,l-1);
Split(mid,t,R,r-l+1);///note: r-l!!
t->lazy += val; ///lazy_update
Merge(mid,L,t);
Merge(t,mid,R);
}
struct info
{
LL x;
int idx;
info() {}
info(LL x, int idx): x(x), idx(idx) {}
bool operator < (const info &p) const
{
return x < p.x;
}
};
vector <info> v;
int effect;
void sub_left(int n, pnode &t, LL x, LL y)
{
int ans = 0;
order_of_key(t, x, 0, ans);
if( ans == 0 ) return;
update(t, 1, ans, -y);
}
void sub_right(int n, pnode &t, LL x, LL y)
{
int ans = 0;
order_of_key(t, x, 0, ans);
if( ans == 0 ) return;
vector <info> v;
for(int i = 1; i <= ans; i++)
{
LL val = ArrayValue(t, i);
v.pb( info(val - y, keep) );
effect++;
}
for(int i = 1; i <= ans; i++) ArrayDelete(t, 1);
for(int i = 0; i < ans; i++)
{
int idx = 0;
order_of_key(t, v[i].x, 0, idx);
ArrayInsert(t, init(v[i].x, v[i].idx), idx + 1);
assert( v[i].x == ArrayValue(t, idx + 1) );
}
}
void add_right(int n, pnode &t, LL x, LL y)
{
int ans = 0;
order_of_key(t, x - 1, 0, ans);
ans++;
if( ans > n ) return;
update(t, ans, n, y);
}
void add_left(int n, pnode &t, LL x, LL y)
{
int ans = 0;
order_of_key(t, x - 1, 0, ans);
ans++;
if( ans > n ) return;
vector <info> v;
for(int i = ans; i <= n; i++)
{
LL val = ArrayValue(t, i);
v.pb( info(val + y, keep) );
effect++;
}
for(int i = ans; i <= n; i++) ArrayDelete(t, ans);
for(int i = ans; i <= n; i++)
{
int idx = 0;
order_of_key(t, v[i-ans].x, 0, idx);
ArrayInsert(t, init(v[i-ans].x, v[i-ans].idx), idx + 1);
assert( ArrayValue(t, idx+1) == v[i-ans].x );
}
}
void solve(int n, int q)
{
int i;
pnode root = init(-INF,0);
Rep(i,n) ArrayInsert(root, init(v[i].x, v[i].idx), i + 1);
LL x, y;
int ins;
rep(i,q)
{
si(ins);
inside(1,ins,2);
sll(x, y);
inside(-1e9,x,1e9);
inside(-1e9,y,1e9);
if( ins == 1 )
{
if( y >= 0 ) sub_left(n, root, x, y);
else sub_right(n, root, x, y);
}
else
{
if( y >= 0 ) add_right(n, root, x, y);
else add_left(n, root, x, y);
}
}
vector <LL> lol(n+5);
rep(i,n)
{
LL my = ArrayValue(root, i);
lol[keep] = my;
}
rep(i,n)
{
if(i > 1) printf(" ");
pl( lol[i] );
}
printf("\r");
NL;
Clear(root);
}
int main()
{
//freopen("input03.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int T, cs, n, i, q, totn = 0, totq = 0;
LL x;
si(T);
inside(1,T,5);
rep(cs,T)
{
v.clear();
sii(n,q);
inside(1,n,1e5);
inside(1,q,1e5);
totn += n;
totq += q;
effect = 0;
rep(i,n)
{
sl(x);
inside(-1e9,x,1e9);
v.pb( info(x,i) );
}
sort( all(v) );
solve(n, q);
assert( effect <= n );
}
assert( n <= 2e5 );
assert( q <= 2e5 );
return 0;
}
Setter: prophet_ov_darkness Alternate Writer: flash_7,codename27
Editorial
Key observation is that we'll only have to start or end the range in event points (points where given segments either start or end). There will be 2N such event points. We'll iterate over them to set the left pointer. And then binary search on right pointer. Finally to check the number of overlap counts we'll run linear search.
Complexity: O(N^2 log N) (This won't pass :) )
Now we'll fix the left pointer by iterating over the event points. Then we'll binary search on event points to fix the right pointer. Now, we'll try to replace the linear search to check overlap with a better approach. We can do two binary searches for this. Let the time frame we are currently checking is [A, B]. Then, overlap count = N — (number of segments that start after B) — (number of segments that end before B)
The complexity of checking is O(log N) here.
We can do this in O(1), with linear pre-computation over all event points. This problem can also be solved with sliding window/ two pointer technique. But to do so, we'll have to sort the event points initially. In this solution, complexity will be dominated by the complexity of the sorting algorithm you are using. We've tried to allow solutions having a maxiumum complexity of O(N log^2 N).
Complexity: O(N log N) or O(N log^2 N)
Solution Code
prophet_ov_darkness
/*
* Judge Solution for ST3
* by Sourav Sen Tonmoy
*/
#include <bits/stdc++.h>
using namespace std;
#define OK cerr << "ok\n"
#define DB(x) cerr << #x << " = " << x << '\n'
const int LIM = 1000000000, MAX = 100005;
int n, p, key;
pair <int, int> arr[MAX];
pair <int, bool> eventPoints[MAX+MAX]; /// false = start
int stAfter[MAX+MAX], enBefore[MAX+MAX];
bool check(int xIdx, int yIdx) {
return (n - stAfter[yIdx] - enBefore[xIdx] >= p);
}
int bs(int idx) {
int low=idx, mid, high=n+n-1, ret=INT_MAX;
while(low <= high) {
mid = (low+high) >> 1;
if(check(idx, mid)) {
ret = min(ret, eventPoints[mid].first);
high = mid-1;
}
else low = mid+1;
}
if(ret > LIM) return INT_MAX;
else return ret-eventPoints[idx].first;
}
int solve() {
int ret = INT_MAX, cnt=0;
sort(eventPoints, eventPoints+n+n);
for(int i=0; i<n+n; i++) {
if(i && eventPoints[i].first == eventPoints[i-1].first) {
enBefore[i] = enBefore[i-1];
}
else enBefore[i] = cnt;
if(eventPoints[i].second) cnt++;
}
cnt = 0;
for(int i=n+n-1; i>=0; i--) {
if(i != n+n+-1 && eventPoints[i].first == eventPoints[i+1].first) {
stAfter[i] = stAfter[i+1];
}
else stAfter[i] = cnt;
if(!eventPoints[i].second) cnt++;
}
for(int i=0; i<n+n; i++) ret = min(ret, bs(i));
return ret;
}
int main() {
// assert(freopen("all.in", "r", stdin));
// assert(freopen("all.out", "w", stdout));
clock_t st = clock();
int test, kase=1;
assert(scanf("%d", &test) == 1);
assert(1 <= test && test <= 30);
while(test--) {
key = 0;
assert(scanf("%d %d", &n, &p) == 2);
assert(1 <= n && n <= 100000);
assert(1 <= p && p <= 100000);
assert(p <= n);
for(int i=0; i<n; i++) {
assert(scanf("%d %d", &arr[i].first, &arr[i].second) == 2);
assert(1 <= arr[i].first && arr[i].first <= LIM);
assert(1 <= arr[i].second && arr[i].second <= LIM);
assert(arr[i].first <= arr[i].second);
eventPoints[key++] = { arr[i].first, false };
eventPoints[key++] = { arr[i].second, true };
}
printf("Case %d: %d\n", kase++, solve());
}
clock_t en = clock();
fprintf(stderr, "%.3f sec\n", (double)(en-st) / (double)CLOCKS_PER_SEC);
return 0;
}
codename27
/*
* Alternate for ST3
* by Kazi Nayeem
*/
//#include <bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<complex>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//4-side
//int xx[] = {0,0,-1,1};
//int yy[] = {-1,1,0,0};
//6-side hexagonal
//int xx[] = {2,-2,1,1,-1,-1};
//int yy[] = {0,0,1,-1,1,-1};
#define popc(a) (__builtin_popcount(a))
//ll bigmod(ll a,ll b,ll m){if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a) % m;return x;}
//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M
#define MX 1005
#define inf 100000000
const double pi = acos(-1.0);
const ll mod = 1000000007ll;
map<int, int> add, del;
void addVal(int a, int v, map<int, int> &now){
if(now.find(a) == now.end())
now[a] = 0;
now[a] += v;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("3.in", "r", stdin);
//freopen("output.txt", "w", stdout);
//freopen("3my3.out", "w", stdout);
int ti, te, n, k, st, en, totaln = 0;
scanf("%d", &ti);
for(te = 1; te <= ti; te++){
add.clear();
del.clear();
scanf("%d %d", &n, &k);
totaln += n;
for(int i = 1; i <= n; i++){
scanf("%d %d", &st, &en);
addVal(st,1,add);
addVal(st,0,del);
addVal(en,0,add);
addVal(en,1,del);
}
int ans = mod;
int cnt = 0, last;
map<int,int>::iterator it1 = add.begin();
for(map<int,int>::iterator it2 = del.begin(); it2 != del.end() && it1 != add.end(); it2++){
while(it1 != add.end() && (((it1->first) < (it2->second)) || (cnt<k))) {
cnt += it1->second;
last = it1->first;
it1++;
}
//printf("->%d %d %d\n", last, it2->first, cnt);
if(cnt>=k && last>=it2->first){
ans = min(ans,(last)-(it2->first));
}
cnt -= it2->second;
}
printf("Case %d: %d\n", te, ans);
}
cerr<<totaln<<endl;
return 0;
}
Setter: bertho_coder Alternate Writer: Tanzir5
Editorial
Notice that, c0 = a0 * b0
As we know that values of c0 and b0(from input), we can derive a0 easily.
So suppose that we know the values a0, a1, a2, ............ ai-1.
Now, ci = a0 * bi + a1 * b(i-1) + a2 * b(i-2) + .......... + a(i-1)*b1+ai* b0 The only unknown variable in this equation is ai. So the polynomial F(x) can be derived by repeating this process n-1 times.
Solution Code
tube_light
#include<bits/stdc++.h>
using namespace std;
#define D(x) cout << #x " = " <<(x) << endl
#define MAX 100000
typedef long long int LL;
vector<int> multiply(vector<int> &a, vector<int> &b){
vector<int> ret;
ret.resize(a.size() + b.size());
int i, j;
for(i = 0; i < (int) a.size(); i++)
for(j = 0; j < (int) b.size(); j++)
ret[i + j] += a[i] * b[j];
while(!ret.back()) ret.pop_back();
return ret;
}
vector<int> a, b, c, orig_c;
int main()
{
//freopen("in.txt", "r", stdin);
int t, n, k, i, v;
scanf("%d", &t);
while(t--){
a.clear(), b.clear(), c.clear();
scanf("%d", &n);
for(i = 1; i <= n; i++){
scanf("%d", &v);
a.push_back(v);
}
scanf("%d", &k);
for(i = 1; i <= k; i++){
scanf("%d", &v);
c.push_back(v);
}
orig_c = c;
for(int p = 0; p < (int) c.size() - (int) a.size() + 1; p++){
for(int l = 0; l < p; l++){
int r = p - l;
if(r < (int) a.size()) c[p] -= (b[l] * a[r]);
}
assert(c[p] % a[0] == 0);
b.push_back(c[p]/a[0]);
}
printf("%d\n", (int) b.size());
for(i = 0; i < (int) b.size(); i++){
printf("%d", b[i]);
if(i + 1 == (int) b.size()) puts("");
else printf(" ");
}
assert(multiply(a, b) == orig_c);
}
return 0;
}
Maxon5
~~~~~
~~~~~
