QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108473#6405. Barkleyberarchegas#TL 464ms6256kbC++172.5kb2023-05-25 04:37:352023-05-25 04:37:36

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-25 04:37:36]
  • 评测
  • 测评结果:TL
  • 用时:464ms
  • 内存:6256kb
  • [2023-05-25 04:37:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 100010;

ll gcd(ll a, ll b) {
    if( b == 0 ) return a;
    return gcd( b , a%b );
}

int n, q;

ll v[maxn];
ll seg[4*maxn];

void update(int node, int l, int r, int i, ll val)
{
    if( i < l || r < i )
        return;

    if( l == r )
    {
        seg[node] = val;
        return;
    }

    int m = ( l + r )/2;

    update( 2*node , l , m , i , val );
    update( 2*node + 1 , m + 1 , r , i , val );

    seg[node] = gcd( seg[2*node] , seg[2*node + 1] );
}

ll query(int node, int l, int r, int i, int j)
{
    if( j < l || r < i )
        return 0;

    if( i <= l && r <= j )
        return seg[node];

    int m = ( l + r )/2;

    ll gcdLeft = query( 2*node , l , m , i , j );
    ll gcdRight = query( 2*node + 1 , m + 1 , r , i , j );

    return gcd( gcdLeft , gcdRight );
}

int bs(int node, int l, int r, int i, ll val)
{
    if( r < i || seg[node]%val == 0 )
        return -1;

    if( l == r )
        return l;

    int m = ( l + r )/2;
    int ansLeft = bs( 2*node , l , m , i , val );

    if( ansLeft != -1 )
        return ansLeft;

    return bs( 2*node + 1 , m + 1 , r , i , val );
}

vector<int> getPoints(int l)
{
    ll curGCD = v[l];
    ll allGCD = query( 1 , 1 , n , l , n );

    vector<int> points;

    while( curGCD != allGCD )
    {
        // cout << "cur = " << curGCD << endl;
        // cout << "allGCD = " << allGCD << endl; 
        int p = bs( 1 , 1 , n , l , curGCD );
        points.push_back( p );

        // cout << p << endl;
        // cout << v[p] << endl;

        curGCD = gcd( curGCD , v[p] );
    }

    points.push_back( n );
    return points;
}

ll query(int l, int r, int k)
{
    if( k == 0 )
        return query( 1 , 1 , n , l , r );

    ll ans = query( l + 1 , r , k - 1 );
    vector<int> points = getPoints( l );

    for(int p: points)
    {
        if( r < p )
            break;

        update( 1 , 1 , n , p , 0 );
        ans = max( ans , query( l , r , k - 1 ) );
        update( 1 , 1 , n , p , v[p] );
    }

    return ans;
}

int main()
{
    cin >> n >> q;

    for(int i = 1 ; i <= n ; i++)
        cin >> v[i];

    for(int i = 1 ; i <= n ; i++)
        update( 1 , 1 , n , i , v[i] );

    for(int i = 1 ; i <= q ; i++)
    {
        int l, r, k;
        cin >> l >> r >> k;

        cout << query( l , r , k ) << endl;
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3384kb

input:

4 4
3 2 6 4
1 3 1
2 4 1
1 4 2
1 4 3

output:

3
2
3
6

result:

ok 4 number(s): "3 2 3 6"

Test #2:

score: 0
Accepted
time: 8ms
memory: 3480kb

input:

100 10000
7 25 33 17 13 33 24 29 11 1 3 19 2 20 33 23 14 24 15 12 3 1 5 13 6 35 15 21 10 34 31 19 7 33 17 26 26 1 19 21 31 5 29 20 18 32 19 18 19 31 11 26 6 19 2 26 23 1 4 2 31 21 29 30 1 14 20 23 14 32 4 34 13 29 5 26 24 29 28 5 26 26 21 19 2 33 2 31 30 3 23 24 26 32 36 21 21 11 5 9
56 57 1
90 97 1...

output:

26
1
1
1
1
1
1
1
31
1
1
1
1
1
26
1
1
1
1
1
1
29
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
21
1
1
1
1
1
19
1
1
1
21
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
3
1
2
1
26
1
1
1
1
1
1
1
7
1
1
1
33
1
1
1
1
1
1
2
1
26
1
1
1
2
1
1
1
1
1
1
26
1
1
1
1
31
1
1
2
1
4
29
1
2
1
1...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 264ms
memory: 3460kb

input:

1000 66666
25 21 18 19 9 34 16 7 36 2 8 10 25 15 34 9 1 34 6 19 20 20 1 16 10 6 10 1 30 34 6 15 15 11 9 4 34 36 27 17 2 2 19 10 4 22 15 16 22 36 27 26 20 23 29 16 27 14 3 31 32 16 5 5 31 13 27 5 17 23 20 19 13 22 30 14 25 13 7 16 10 6 1 6 3 5 36 1 33 22 31 26 28 3 14 14 2 31 35 7 19 30 36 5 3 14 14 ...

output:

1
2
1
1
1
1
1
1
1
1
1
3
1
2
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
17
1
1
1
20
1
1
1
7
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
7
1
2
15
1
3
1
2
1
1
3
4
1
1
1
1
1
31
1
1
1
2
1
1
1
1
27
3
1
1
1
1
4
10
1
1
1
1
17
1
1
1
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
8
1
1
17
1
2
1
1
1
30
1
25
1
35
1...

result:

ok 66666 numbers

Test #4:

score: 0
Accepted
time: 337ms
memory: 3772kb

input:

10000 66666
35 30 29 34 3 25 23 29 30 32 34 1 25 1 23 11 10 24 33 25 14 1 16 25 33 5 19 2 16 1 19 14 34 6 26 25 36 35 1 32 35 27 18 3 7 16 10 25 6 21 36 31 24 17 20 12 30 21 25 31 27 22 5 19 6 16 7 26 15 21 32 11 34 4 7 25 34 3 14 13 10 1 28 8 12 24 34 27 17 8 17 32 23 30 23 8 19 22 2 11 23 10 4 30 ...

output:

1
16
2
2
1
23
1
1
1
2
1
3
5
1
1
2
1
1
1
1
30
1
1
1
3
18
1
1
1
1
2
1
1
1
1
1
1
1
1
2
2
1
6
36
1
1
2
19
2
1
1
1
1
1
2
1
1
1
21
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
1
1
29
1
1
30
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
2
1
1
1
2
29
1
1
14
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
2
3
1
9
5
1
2
2
1
32
1
1
1
3
2
1
1
...

result:

ok 66666 numbers

Test #5:

score: 0
Accepted
time: 424ms
memory: 6256kb

input:

100000 66666
7 27 21 15 35 19 32 8 1 30 6 3 33 29 25 5 1 24 34 9 13 27 9 32 20 26 5 10 1 30 29 15 11 31 12 27 10 32 14 30 27 6 16 17 16 36 12 35 18 4 14 9 12 33 1 10 27 31 16 27 16 15 6 16 28 16 26 6 25 23 23 31 22 16 30 33 15 2 27 11 18 23 3 2 23 2 13 17 21 15 4 2 19 22 35 35 13 28 9 30 20 29 17 5 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
2
1
1
7
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
29
1
1
1
1
1
1
1
1
1
1
1
35
3
1
1
20
1
1
1
1
1
1
1
1
1
2
1
1
2
1
1
19
1
1
1
1
1
1
1
1
1
1
1
1
1
1
25
1
1
1
1
1
1
2
13
1
9
25
1
1
1
1
1
1
1
1
2
1
1
1
25
1
18
4
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
23
1
1
1
1
1
33
2...

result:

ok 66666 numbers

Test #6:

score: 0
Accepted
time: 464ms
memory: 6184kb

input:

100000 66666
450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 450283905890997363 45...

output:

450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997363
450283905890997...

result:

ok 66666 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

100000 66666
701982420492091392 592297667290202112 789730223053602816 369768517790072832 526486815369068544 562220051373121536 701982420492091392 701982420492091392 444223250467651584 592297667290202112 554652776685109248 888446500935303168 623984373770747904 888446500935303168 888446500935303168 55...

output:

9795520512
9795520512
352638738432
9795520512
29386561536
39182082048
117546246144
9795520512
19591041024
9795520512
29386561536
352638738432
176319369216
9795520512
9795520512
58773123072
176319369216
29386561536
9795520512
9795520512
117546246144
29386561536
9795520512
58773123072
117546246144
117...

result: