QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125002#2788. Horsessomethingnew#20 240ms48808kbC++204.0kb2023-07-15 22:13:102024-07-04 00:42:25

Judging History

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

  • [2024-07-04 00:42:25]
  • 评测
  • 测评结果:20
  • 用时:240ms
  • 内存:48808kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-15 22:13:10]
  • 提交

answer

//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "horses.h"
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
struct segtree {
    int sz;
    vector<int> tree;
    void init(int n, vector<int> a) {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.assign(sz * 2, {});
        for (int i = 0; i < n; ++i) {
            tree[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
        }
    }
    int get(int l, int r) {
        l += sz;
        r += sz;
        int res = 0;
        while (l <= r) {
            if (l % 2) {
                res = max(res, tree[l]);
                l++;
            }
            if (r % 2 == 0) {
                res = max(res, tree[r]);
                r--;
            }
            l /= 2;
            r /= 2;
        }
        return res;
    }
    void ch(int v, int x) {
        v += sz;
        tree[v] = x;
        while (v != 1) {
            v /= 2;
            tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
        }
    }
};
struct segtreemult {
    int sz;
    vector<ll> tree;
    void init(int n, vector<int> a) {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.assign(sz * 2, {});
        for (int i = 0; i < n; ++i) {
            tree[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            tree[i] = tree[i * 2] * tree[i * 2 + 1] % mod;
        }
    }
    int get(int l, int r) {
        l += sz;
        r += sz;
        ll res = 1;
        while (l <= r) {
            if (l % 2) {
                res = res * tree[l] % mod;
                l++;
            }
            if (r % 2 == 0) {
                res = res * tree[r] % mod;
                r--;
            }
            l /= 2;
            r /= 2;
        }
        return res;
    }
    void ch(int v, int x) {
        v += sz;
        tree[v] = x;
        while (v != 1) {
            v /= 2;
            tree[v] = tree[v * 2] * tree[v * 2 + 1] % mod;
        }
    }
};
set<int> nonzeroes;
segtree sgmax;
segtreemult sgmult;
vector<int> a, b;
ll getval() {
    ll reba = 1;
    auto it = nonzeroes.end();
    vector<int> elems;
    while (it != nonzeroes.begin()) {
        it--;
        reba *= a[*it];
        elems.push_back(*it);
        if (reba > (int)1e9)
            break;
    }
    if (reba <= (int)1e9 and elems.back() != 0)
        elems.push_back(0);
    ll nst = sgmult.get(0, elems.back());
    reverse(all(elems));
    vector<int> elel(elems.size());
    for (int i = 0; i < elems.size(); ++i) {
        if (i + 1 < elems.size())
            elel[i] = sgmax.get(elems[i], elems[i + 1] - 1);
        else
            elel[i] = sgmax.get(elems[i], (int)a.size() - 1);
    }
    vector<ll> valval(elems.size());
    ll boba = 1;
    for (int i = 0; i < elems.size(); ++i) {
        if (i != 0)
            boba *= a[elems[i]];
        valval[i] = boba * elel[i];
    }
    return (*max_element(all(valval))) % mod * nst % mod;
}
int init(int N, int X[], int Y[]) {
    a.assign(N, 0);
    b.assign(N, 0);
    nonzeroes.clear();
    for (int i = 0; i < N; ++i) {
        a[i] = X[i];
        b[i] = Y[i];
        if (a[i] != 1)
            nonzeroes.insert(i);
    }
    sgmax.init(N, b);
    sgmult.init(N, a);
    return getval();
}
int updateX(int pos, int val) {
    if (a[pos] != 1)
        nonzeroes.erase(pos);
    a[pos] = val;
    if (a[pos] != 1)
        nonzeroes.insert(pos);
    sgmult.ch(pos,val);
    return getval();
}
int updateY(int pos, int val) {
    sgmax.ch(pos,val);
    return getval();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 17
Accepted
time: 0ms
memory: 3768kb

input:

1
2
3
0

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

10
2 1 1 5 2 1 1 10 5 1
3 5 7 9 4 1 4 10 10 9
0

output:

10000

result:

ok single line: '10000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4020kb

input:

10
10 10 10 1 1 1 1 1 1 1
2 3 4 2 7 6 5 4 3 2
0

output:

7000

result:

ok single line: '7000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

10
9 1 1 1 1 1 1 1 1 2
4 1 1 1 1 1 1 1 1 2
0

output:

36

result:

ok single line: '36'

Test #5:

score: -17
Runtime Error

input:

10
1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10
0

output:

Unauthorized output

result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 20
Accepted

Test #33:

score: 20
Accepted
time: 149ms
memory: 48724kb

input:

500000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

967631222
967631222
795463654
885679347
618832158
618832158
618832158
618832158
618832158
582471866
864166718
864166718
864166718
864166718
864166718
813424701
813424701
813424701
813424701
813424701
815547130
815547130
815547130
815547130
815547130
715585103
715585103
715585103
715585103
715585103
...

result:

ok 100001 lines

Test #34:

score: 0
Accepted
time: 216ms
memory: 48668kb

input:

500000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000...

output:

764523385
560650427
560650427
711685442
711685442
711685442
630166054
630166054
630166054
604940491
56866480
384893091
501798659
560422885
560422885
18199764
63591615
212319888
212319888
39499230
828983454
828983454
634555752
4896305
181214713
231675794
231675794
966365836
181367397
181367397
987190...

result:

ok 100001 lines

Test #35:

score: 0
Accepted
time: 193ms
memory: 48808kb

input:

500000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

967631222
192947708
884245369
884245369
884245369
884245369
884245369
649885822
981487169
321173457
159089267
159089267
159089267
747556995
964496384
964496384
964496384
928334020
928334020
928334020
928334020
459124375
459124375
404955269
251629123
80789828
80789828
463250667
463250667
120836466
57...

result:

ok 100001 lines

Test #36:

score: 0
Accepted
time: 240ms
memory: 48584kb

input:

500000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

628833504
223286077
463897870
972304401
127408916
377483838
722400213
221924185
818717195
473021697
502484429
318341012
230123148
522240493
607202268
818940989
569566927
384659940
448632730
578079312
667605482
963648869
939506632
965323855
498894254
695643284
699407581
168605135
70361400
795950777
1...

result:

ok 100001 lines

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%