QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#858011#147. Floppybinminh010 40ms9188kbC++209.4kb2025-01-16 12:16:432025-01-16 12:16:43

Judging History

This is the latest submission verdict.

  • [2025-01-16 12:16:43]
  • Judged
  • Verdict: 0
  • Time: 40ms
  • Memory: 9188kb
  • [2025-01-16 12:16:43]
  • Submitted

floppy

#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define ret(s) return void(cout << s);

constexpr int mod = 1e9 + 7, mod2 = 998244353;
constexpr double eps = 1e-9;
const double PI = acos(-1);
constexpr ull npos = string::npos;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using cd = complex<double>;
mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 mt64(chrono::system_clock::now().time_since_epoch().count());
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<cd> vcd;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;

ll add(ll a, ll b, int m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);a+=b;return a >= m ? a - m: a;}
ll sub(ll a, ll b, int m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);a-=b;return a < 0 ? a + m: a;}
ll mul(ll a, ll b, int m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);return a*b % m;}
ll bin_mul(ll a, ll b, ll m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);ll x = 0;while (b) {if (b & 1) x = (x + a) % m;a = (a + a) % m;b>>=1;}return x;}
ll bin_pow(ll a, ll b, ll m) {ll x = 1;a = (a >= m ? a % m: a); while (b) {if (b & 1) x = bin_mul(x, a, m);a = bin_mul(a, a, m);b>>=1;}return x;}
ll power(ll a, ll b, int m) {ll x = 1;a = (a >= m ? a % m: a); while (b) {if (b & 1) x = x*a % m;a = a*a % m;b>>=1;}return x;}
ll power(ll a, ll b) {ll x = 1;while (b) {if (b & 1) x = x*a;a = a*a;b>>=1;}return x;}
ll ceil(ll a, ll b) {return (a + b - 1)/b;}
ll to_int(const string &s) {ll x = 0; for (int i = (s[0] == '-'); i < sz(s); ++i) x = x*10 + s[i] - '0';return x*(s[0] == '-' ? -1: 1);}
bool is_prime(ll n) {if (n < 2) return 0;if (n < 4) return 1;if (n % 2 == 0 || n % 3 == 0) return 0;for (ll i = 5; i*i <= n; i+=6) {if(n % i == 0 || n % (i + 2) == 0) return 0;}return 1;}
bool is_square(ll n) {ll k = sqrt(n); return k*k == n;}
ll factorial(int n) {ll x = 1;for (int i = 2; i <= n; ++i) x*=i;return x;}
ll factorial(int n, int m) {ll x = 1;for (ll i = 2; i <= n; ++i) x = x*i % m;return x;}
bool is_power(ll n, ll k) {while (n % k == 0) n/=k;return n == 1ll;}
string str(ll n) {if (n == 0) return "0"; string s = ""; bool c = 0; if (n < 0) c = 1, n = -n; while (n) {s+=n % 10 + '0'; n/=10;} if (c) s+='-'; Reverse(s); return s;}
string repeat(const string &s, int n) {if (n < 0) return ""; string x = ""; while (n--) x+=s; return x;}
string bin(ll n) {string s = ""; while (n) {s+=(n & 1) + '0'; n>>=1;} Reverse(s); return s;}
void sieve(vector<bool> &a) {int n = a.size(); a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(bool a[], int n) {a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(vector<int> &a) {int n = a.size(); for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
void sieve(int a[], int n) {for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
vector<pii> factorize(int n) {vector<pii> a; for (int i = 2; i*i <= n; ++i) {if (n % i == 0) {int k = 0; while (n % i == 0) ++k, n/=i; a.emplace_back(i, k);}} if (n > 1) a.emplace_back(n, 1); return a;}
int rand(int l, int r) {return uniform_int_distribution<int>(l, r)(mt);}
ll rand(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(mt64);}
int Log2(int n) {return 31 - __builtin_clz(n);}
ll Log2(ll n) {return 63 - __builtin_clzll(n);}
template<class T> void compress(vector<T> &a) {vector<T> b; for (T &i: a) b.push_back(i); sort(all(b)); b.resize(unique(all(b)) - b.begin()); for (T &i: a) i = lower_bound(all(b), i) - b.begin();}
template<class A, class B> bool ckmin(A &a, const B &b) {return a > b ? a = b, 1: 0;}
template<class A, class B> bool ckmax(A &a, const B &b) {return a < b ? a = b, 1: 0;}

template<class A, class B> istream& operator>>(istream& in, pair<A, B> &p) {in >> p.first >> p.second; return in;}
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &p) {out << p.first << ' ' << p.second; return out;}
template<class T> istream& operator>>(istream& in, vector<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<T> &a) {for (auto &i: a) out << i << ' '; return out;}
template<class T> istream& operator>>(istream& in, vector<vector<T>> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<vector<T>> &a) {for (auto &i: a) out << i << '\n'; return out;}
template<class T> istream& operator>>(istream& in, deque<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const deque<T> &a) {for (auto &i: a) out << i << ' '; return out;}
// istream& operator>>(istream& in, __int128_t &a) {string s; in >> s; a = 0; for (auto &i: s) a = a*10 + (i - '0'); return in;}
// ostream& operator<<(ostream& out, __int128_t a) {string s = ""; if (a < 0) s+='-', a = -a; if (a == 0) s+='0'; while (a > 0) {s+=(int)(a % 10) + '0'; a/=10;} Reverse(s); out << s; return out;}

#include "floppy.h"
void read_array(int subtask_id, const vi &a) {
    int n = sz(a);
    vector<vpair> s(16, vpair(n));
    For(i,0,n) s[0][i] = {a[i], i};
    For(i,1,16) {
        FOR(j,0,n-(1<<i)) s[i][j] = max(s[i - 1][j], s[i - 1][j + (1 << (i - 1))]);
    }
    auto get = [&](int l, int r) {
        int i = __lg(r - l + 1);
        return max(s[i][l], s[i][r - (1 << i) + 1]).second;
    };
    string t;
    auto dfs = [&](auto &&dfs, int l, int r)->void{
        int i = get(l, r);
        t+='0' + (l < i); t+='0' + (i < r);
        if (l < i) dfs(dfs, l, i - 1);
        if (i < r) dfs(dfs, i + 1, r);
    };
    dfs(dfs, 0, n - 1);
    save_to_floppy(t);
}
vi solve_queries(int subtask_id, int n, const string &t, const vi &a, const vi &b) {
    vvi p(16, vi(n)), g(n);
    vi h(n);
    int k = 0, x = 0;
    auto dfs = [&](auto &&dfs, int i)->pii{
        //{size, vertex}
        k+=2;
        int u = 0, w = 1;
        if (t[i] == '0') u = x;
        else {
            auto [s, v] = dfs(dfs, i + 2);
            w+=s;
            u = x;
            p[0][v] = u; g[u].pb(v);
        }
        ++x;
        if (t[i + 1] == '1') {
            auto [s, v] = dfs(dfs, k);
            w+=s;
            p[0][v] = u; g[u].pb(v);
        }
        return {w, u};
    };
    dfs(dfs, 0);
    auto high = [&](auto &&high, int u)->void{
        trav(v,g[u]) h[v] = h[u] + 1, high(high, v);
    };
    high(high, 0);
    For(i,1,16) For(j,0,n) p[i][j] = p[i - 1][p[i - 1][j]];
    auto lca = [&](int u, int v)->int{
        if (h[u] < h[v]) swap(u, v);
        int d = h[u] - h[v];
        Fore(i,15,0) if (d >> i & 1) u = p[i][u];
        if (u == v) return u;
        Fore(i,15,0){
            if (p[i][u] != p[i][v]) u = p[i][u], v = p[i][v];
        }
        return p[0][u];
    };
    vi c(sz(a));
    For(i,0,sz(a)) c[i] = lca(a[i], b[i]);
    return c;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3968kb

input:

1 496
484
491
478
483
452
446
458
493
453
457
468
418
440
241
267
365
462
441
495
39
54
70
26
97
152
24
105
85
170
298
42
275
305
295
297
207
211
296
184
346
98
123
171
157
135
194
243
156
115
196
169
53
138
93
263
251
201
195
333
324
396
338
270
311
359
289
290
486
403
183
339
310
473
464
471
469
4...

output:

992
11111100110010010011100011110010100000111111111111111011101110000011000010001100111000001111111011100001001101000111000001010000110110001000111111011100001100001110110001001111000001111000001111101001010000001111000011111100000010001111111101110110000111000011001111110111000101000101100011111100...

input:

1 496
992
11111100110010010011100011110010100000111111111111111011101110000011000010001100111000001111111011100001001101000111000001010000110110001000111111011100001100001110110001001111000001111000001111101001010000001111000011111100000010001111111101110110000111000011001111110111000101000101100011...

output:

18
1
115
0
18
0
0
7
0
1
7
0
18
0
18
0
18
1
305
7
18
7
18
18
305
18
18
1
1
0
0
18
0
0
1
18
115
7
1
1
1
18
115
0
18
18
18
18
18
115
18
1
1
252
0
1
7
1
1
1
18
305
1
18
18
0
0
0
18
18
18
7
18
18
1
1
7
1
18
18
0
1
0
7
18
240
18
373
18
1
7
18
18
0
0
0
18
18
1
1
7
18
18
18
18
1
7
7
0
67
18
1
18
18
476
0
1
...

result:

wrong answer wrong answer on query #1 (a = 109, b = 205): read 18 but expected 115

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 8ms
memory: 5192kb

input:

2 9998
941669562
945620824
923950848
951745929
487936934
545172907
544098433
249251812
620978276
575815248
584717207
588068187
353162497
679201670
592738155
438327774
762119945
576801563
408534366
592715009
525377786
603981493
-93758897
137509462
-38676966
-36724784
654920761
-595506762
-645387884
-...

output:

19996
111111111111000011111111110001001110000001001111110100001100100011111111101010100100010011111101010000011111000001001100001111100000010111000100111011110000001110100011111101100000101011000100111111000011010000010011001111011000111110001111111111100100110100011001001000100110010011110010100110...

input:

2 9998
19996
11111111111100001111111111000100111000000100111111010000110010001111111110101010010001001111110101000001111100000100110000111110000001011100010011101111000000111010001111110110000010101100010011111100001101000001001100111101100011111000111111111110010011010001100100100010011001001111001...

output:

359
0
359
359
3
6131
247
6131
359
5760
1
359
1
359
3
6131
6131
3
6131
6131
6131
0
247
5760
247
6131
247
3
5760
6664
6131
6131
359
247
359
5760
1
359
5760
3
1
359
5760
359
3
359
247
1
0
5760
6131
1
359
0
247
247
6131
6131
0
6131
359
3
0
359
0
1
247
3
6131
3
3
359
359
359
0
1
359
5760
3
6131
6131
3
0
...

result:

wrong answer wrong answer on query #1 (a = 2131, b = 6955): read 359 but expected 6131

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 40ms
memory: 9188kb

input:

3 39995
922975946
766568552
929754744
983095922
988967630
879723897
928174186
951250463
831467029
836738151
464712826
467214506
167661408
156498284
426000721
530835328
-35115993
-86200136
327603078
448684869
192895652
125768327
402822176
196767853
409109378
985776352
976681898
967347754
989156210
99...

output:

79990
111111111111111110111010010011111000110011110010010011100100101101000001001011100000111111111101010100110000110011110111000010110010000011110111011010100010001100111111000000010110101000110011101111111111010010010010010011100010001111101010000011001000110110001110000101110001001000111111001111...

input:

3 39995
79990
1111111111111111101110100100111110001100111100100100111001001011010000010010111000001111111111010101001100001100111101110000101100100000111101110110101000100011001111110000000101101010001100111011111111110100100100100100111000100011111010100000110010001101100011100001011100010010001111...

output:

4
3597
39520
29
16794
7409
29
3
554
39520
29
2
29
28
3
35
4
554
29
35
554
28
28
2
4
35
39520
0
17919
37333
3
434
3
4
434
39520
554
35
39520
3
39520
35
4
29
17919
554
0
4
35
4
554
17919
17919
28
28370
2
35
35
333
2
434
17919
4
3
3597
28
333
29
4
333
584
17919
35
27076
35
35
2
554
39520
39520
2
39520
...

result:

wrong answer wrong answer on query #1 (a = 9100, b = 12589): read 4 but expected 11215