vERY gOOd AtcodeR,making mY cOdE SpIn.

有中国人吗？

is this hard?

You are right. But G is only 575 pts?

Hope everyone to have fun! And I hope a positive delta.I've already got negative deltas for a long time(only 4 probs)...

Hope for a funny and relaxing contest on International Children's Day.

Happy Children's Day!

Good luck.

Happy Children's day!

My post contest discussion stream for A-F problems

Interesting problems, this was a bit tougher than 355. My second ABC and it feels so much more diverse and balanced than recent CF rounds, great job.

Sadly rounding down in E ruins such a beautiful solution:

for a in aa {
    sum -= a;
    ans += sum / a;
}

Couldn't find fix for it.

Why O(max(a) * log(max(a))) gives TLE in E?

Whats the mistake in my code for problem-C ? Code

Why is today's G only worth 575 points? I think it is as hard as last round's G, which is 650 points. (and the statistics agrees with me too!)

What's the matter with my segment tree algorithm on problem E?

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
pair<long long,long long>b[200010];
long long n,a[200010],tree1[800010],tree2[800010],lazy[800010];
map<pair<long long,long long>,long long>id;
void change1(long long now,long long l,long long r,long long x,long long k)
{
	if(r<x||l>x) return;
	if(l==r)
	{
		tree1[now]=k;
		return;
	}
	long long mid=(l+r)>>1;
	if(x<=mid) change1(now<<1,l,mid,x,k);
	else change1(now<<1|1,mid+1,r,x,k);
	tree1[now]=tree1[now<<1]+tree1[now<<1|1];
}
long long find1(long long now,long long l,long long r,long long x,long long y)
{
	if(r<x||l>y) return 0;
	if(x<=l&&r<=y) return tree1[now];
	long long mid=(l+r)>>1,res=0;
	if(x<=mid) res+=find1(now<<1,l,mid,x,y);
	if(y>mid) res+=find1(now<<1|1,mid+1,r,x,y);
	return res;
}
void push_down(long long now,long long l,long long r)
{
	long long mid=(l+r)>>1;
	lazy[now<<1]=lazy[now];
	lazy[now<<1|1]=lazy[now];
	tree2[now<<1]+=lazy[now]*(mid-l+1);
	tree2[now<<1|1]+=lazy[now]*(r-mid);
	lazy[now]=0;
}
void change2(long long now,long long l,long long r,long long x,long long y,long long k)
{
	if(r<x||l>y) return;
	if(x<=l&&r<=y)
	{
		lazy[now]=k;
		tree2[now]+=k*(r-l+1);
		return;
	}
	push_down(now,l,r);
	long long mid=(l+r)>>1;
	if(x<=mid) change2(now<<1,l,mid,x,y,k);
	if(y>mid) change2(now<<1|1,mid+1,r,x,y,k);
	tree2[now]=tree2[now<<1]+tree2[now<<1|1];
}
long long find2(long long now,long long l,long long r,long long x,long long y)
{
	if(r<x||l>y) return 0;
	if(x<=l&&r<=y) return tree2[now];
	push_down(now,l,r);
	long long mid=(l+r)>>1,res=0;
	if(x<=mid) res+=find2(now<<1,l,mid,x,y);
	if(y>mid) res+=find2(now<<1|1,mid+1,r,x,y);
	return res;
}
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i].first=a[i];
		b[i].second=i;
	}
	stable_sort(b+1,b+n+1);
	for(long long i=1;i<=n;i++) id[b[i]]=i;
	long long ans=0;
	for(long long i=1;i<=n;i++)
	{
		long long tmp=id[make_pair(a[i],i)];
		long long tmp2=find1(1,1,n,tmp+1,n);
		ans+=tmp2/a[i];
		change1(1,1,n,tmp,1);
		change2(1,1,n,1,tmp-1,a[i]);
	}
	for(long long i=1;i<=n;i++)
	{
		long long tmp=find2(1,1,n,1,i-1);
		if(tmp==0) continue;
		ans+=tmp/b[i].first;
	}
	printf("%lld\n",ans);
}

It can't even AC any of the examples.

Can someone explain why my logics for C & D fail?

For C, I iterate over each possible subset and check if it does not contradict with the tests.

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int n, m, k;
set<int> st;
set<set<int>> ans;
vector<vector<vector<int>>> test(2);

void Generate(int cur) {
  if (cur - 1 > n) {
    return;
  }
  if ((int)st.size() >= k) {
    bool ok = true;
    for (int t = 0; t <= 1; t++) {
      for (auto& vec : test[t]) {
        int cnt = 0;
        for (auto& x : vec) {
          if (st.count(x)) {
            cnt++;
          }
        }
        if (t == 1 && cnt < k) {
          ok = false;
        }
        if (t == 0 && cnt >= k) {
          ok = false;
        }
      }
    }
    if (ok) {
      ans.insert(st);
    }
  }
  st.insert(cur);
  Generate(cur + 1);
  st.erase(cur);
  Generate(cur + 1);
}

void Solve() {
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int sz;
    cin >> sz;
    vector<int> v(sz);
    for (int j = 0; j < sz; j++) {
      cin >> v[j];
    }
    char c;
    cin >> c;
    if (c == 'o') {
      test[1].push_back(v);
    } else {
      test[0].push_back(v);
    }
  }
  Generate(1);
  cout << (int)ans.size() << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt = 1;
//  cin >> tt;
  for (int i = 0; i < tt; i++) {
    Solve();
  }
  return 0;
}

For D, I iterate over 1's in M, and count the number of 1's on i's position through k: 0->N. The counting can be done in O(1) since on i's position 0's and 1's are alternating like this: 01010101 (for bit 0) 00110011 (for bit 1) 00001111 (for bit 2) ...

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

const ll MOD = 998244353;

void Solve() {
  ll n, m;
  cin >> n >> m;
  ll ans = 0;
  for (int i = 0; i < 60; i++) {
    if (m & (1ll << i)) {
      ll tmp = n / (1ll << (i + 1)) * (1ll << (i + 1));
      ll add = tmp / 2 % MOD;
      add = (add + max(0ll, (n - tmp) - (1ll << i))) % MOD;
      ans = (ans + add) % MOD;
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt = 1;
//  cin >> tt;
  for (int i = 0; i < tt; i++) {
    Solve();
  }
  return 0;
}

for E : How to find the remainder of the values which are greater than a[i] for every a[i] efficiently.

Problem F can be solved by dividing into sqrt(Q) blocks of queries :D, I love sqrt decomposition.

why range based segment tree won't work for Problem F ?

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Bird
{
    int Value; // Minimum value of a segment
    Bird *LeftChild, *RightChild; // Pointers to left child and right child

    Bird() // Constructor
    {
        Value = 0;
        LeftChild = NULL;
        RightChild = NULL;
    }

    void BirdLay() // Construct Childs
    {
        if (LeftChild == NULL) LeftChild = new Bird();
        if (RightChild == NULL) RightChild = new Bird();
    }
};

Bird* Root = new Bird(); // The first Node that manage [1, N]
Bird* Root1 = new Bird(); // The first Node that manage [1, N]


void BirdPerch(Bird *Current, int curL, int curR, int Pos, int newValue)
{
    if (curL > Pos || curR < Pos) { // Pos is not in range [curL, curR]
        return;
    }

    if (curL == curR) { // Current is the Node that manage only Posth element
        Current -> Value = newValue;
        return;
    }

    int mid = (curL + curR) / 2;
    Current -> BirdLay();
    BirdPerch(Current -> LeftChild, curL, mid, Pos, newValue);
    BirdPerch(Current -> RightChild, mid + 1, curR, Pos, newValue);
    Current -> Value = (Current -> LeftChild -> Value +
                           Current -> RightChild -> Value);
}

int BirdFly(Bird *Current, int curL, int curR, int L, int R)
{
    if (curL > R || curR < L) { // [curL, curR] doesn't intersect with [L, R]
        return 0;
    }

    if (L <= curL && curR <= R) { // [curL, curR] is inside [L, R]
        return Current -> Value;
    }

    int mid = (curL + curR) / 2;
    Current -> BirdLay();
    return (BirdFly(Current -> LeftChild, curL, mid, L, R) +
               BirdFly(Current -> RightChild, mid + 1, curR, L, R));
}



int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N;
    int q;
    int k;
    cin>>k;
    Q = N;

    char Type;
    int Pos, newValue, L, R;

    int mt = 1e16;

    for(int i = 0; i < N; i++){
        int t;
        cin>>t;
        if(t == 1){

            int x;
            cin>>x;
            int s = BirdFly(Root1, 1, mt, x, x);
            if(s == 1){ // if already there delete it
                //cout<<x<<endl;
                BirdPerch(Root1, 1, mt, x, -1);
            } else {
                BirdPerch(Root1, 1, mt, x, 1);
            }
        } else {
            int x;
            cin>>x;
            int s = BirdFly(Root1, 1, mt, max(1ll*0, x - k), x + k);
            cout<<s<<endl;
        }

    }
    //cout<<res<<endl;
}

Problem setter, I don't know who you are, but I love you, you are amazing! =)

I laughed so hard when I solved problem C and read the problem statement of D =))))

Problem A is very ez, but was so satisfying to solve with clean c++ std. Pure joy =))

vector<int> v(n);
iota(v.begin(), v.end(), 1);
reverse(v.begin() + l - 1,v.begin() + r);
copy(v.begin(), v.end(), ostream_iterator<int>(std::cout, " "));

How to solve problem E. The editorial is too complex for me.

MySolution Can anyone please tell me what is wrong in my solution for C — Keys? ;)

What is error in my C code : https://atcoder.jp/contests/abc356/submissions/54135408?

In F, I used DCP offline on unordered_maps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#pragma GCC optimize("unroll-loops,O3")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define cok cout << (ok ? "YES\n" : "NO\n");
#define dbg(x) cout << (#x) << ": " << x << endl;
#define dbga(x,l,r) cout << (#x) << ": "; for (int ii=l;ii<r;ii++) cout << x[ii] << " "; cout << endl;
#define int long long
#define pi pair<int, int>
const int N = 1e6+9;
struct Q {
    int l, r, x;
};
int res[N], k, q;
unordered_map<int, int> p, sz;
vector<pi> memp[N], memsz[N];
vector<int> del[N];
set<int> st;
int in;
int find(int x) {return x == p[x] ? x : find(p[x]);}
void merge(int a, int b) {
    if (b == -1 || abs(a - b) > k) return;
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    memp[in].pb({a, p[a]});
    memsz[in].pb({b, sz[b]});
    p[a] = b;
    sz[b] += sz[a];
}
int get_ans(int x) {
    return sz[find(x)];
}
void add(int x) {
    memp[in].pb({x, 0});
    memsz[in].pb({x, 0});
    del[in].pb(x);
    auto it = st.upper_bound(x);
    int rp = it == st.end() ? -1 : *it;
    int lp = it == st.begin() ? -1 : *(--it);
    st.insert(x);
    sz[x] = 1;
    p[x] = x;
    merge(x, lp);
    merge(x, rp);
}
void save() {
    in++;
}
void roll() {
    while (memp[in].size()) {
        auto [pos, val] = memp[in].back();
        p[pos] = val;
        memp[in].pop_back();
        auto [pos2, val2] = memsz[in].back();
        sz[pos2] = val2;
        memsz[in].pop_back();
    }
    while (del[in].size()) {
        int x = del[in].back();
        st.erase(x);
        del[in].pop_back();
    }
    in--;
}
void DAC(int lx, int rx, vector<Q> zap) {
    save();
    if (rx - lx == 1) {
        for (auto [l, r, x]: zap) {
            if (l != -1 && l <= lx && lx < r) {
                add(x);
            }
        }
        for (auto [l, r, x]: zap) {
            if (l == -1 && r == lx) {
                res[r] = get_ans(x);
            }
        }
    } else {
        int m = lx + rx >> 1;
        vector<Q> vpush;
        for (auto [l, r, x]: zap) {
            if (l == -1) {
                if (lx <= r && r < rx) vpush.pb({l, r, x});
            } else if (l <= lx && rx <= r) add(x);
            else if (min(r, rx) > max(l, lx)) vpush.pb({l, r, x});
        }
        DAC(lx, m, vpush);
        DAC(m, rx, vpush);
    }
    roll();
}
signed main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> q >> k;
    set<int> st;
    map<int, int> lst;
    vector<Q> vec;
    for (int i = 0; i < q; i++) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            if (st.count(x)) {
                vec.pb({lst[x], i, x});
                st.erase(x);
            } else {
                st.insert(x);
                lst[x] = i;
            }
        } else {
            vec.pb({-1, i, x});
        }
    }
    for (int x: st) {
        vec.pb({lst[x], q, x});
    }
    for (int i = 0; i < q; i++) res[i] = -1;
    DAC(0, q, vec);
    for (int i = 0; i < q; i++) if (res[i] != -1) cout << res[i] << "\n";
}

Atcoder should have a NO AI TEST

F using binary search and segment tree. For a x, we need to know the leftmost element having absolute different with element to it's left > k. In the same way we will find the rightmost element having absolute different with element to it's right > k. Now we have 2 indexes a and b. The answer will be no of element in the range [a, b] which are still part of S. Sorry for my bad English.

for e may someone tell me what is matter of my code?

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

typedef long long LL;
int a[N], cnt[N];
LL s[N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        cnt[a[i]] ++;
    }
    // x --- 2x - 1 --> 1; 2x --- 3x - 1 --> 2
    for(int i = 1; i <= 1000000; i ++ ) s[i] = s[i - 1] + cnt[i];
    LL ans = 0;
    for(int i = 1; i <= 1000000; i ++ ) {
        if(!cnt[i]) continue;
        for(int j = i; j <= 1000000; j += i) {
            int r = min(j + i - 1, 1000000);
            ans += (long long)cnt[i] * (s[r] - s[j - 1]) * (r / i);
        }
        if(cnt[i] > 1) {
            ans -= cnt[i];
            ans += ((long long)cnt[i] * cnt[i] - 1) / 2;
        }
    }
    cout << ans - n;
    return 0;
}

In problem C, the following solution of mine got AC. I thought it would be a TLE. What I did is calculate for every combination using bitmask. In worse case it is O((2^N)*M*N)=O((2^15)*100*15)=49,152,000. Can someone please explain why is it not TLE?

my solution

a complete beginner here, where would one rate the difficulty of this challenge? This was my first CC at I could only crack the first two.

https://atcoder.jp/contests/abc356/submissions/54163403

Any idea why a simple functional implementation would give wrong answer rather than tle?

Where can one find the complete set of test cases for problem E for this contest?