QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114095#6564. Frequent FlierUFRJ#AC ✓73ms19272kbC++201.4kb2023-06-20 22:46:542023-06-20 22:46:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-20 22:46:55]
  • 评测
  • 测评结果:AC
  • 用时:73ms
  • 内存:19272kb
  • [2023-06-20 22:46:54]
  • 提交

answer

#include "bits/stdc++.h"

using lint = int64_t;

using namespace std;

template<typename T> struct FT{
    vector<T> s;
    FT(int n) : s(n) {}
    void update(int pos, T dif){
        for(; pos < (int) s.size(); pos |= pos + 1) s[pos] += dif;
    }
    T query(int pos){
        T res = 0 ;
        for(; pos > 0; pos &= pos - 1) res += s[pos-1];
        return res;
    }
    T query(int a, int b){ //[a, b)
        return query(b) - query(a);
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    set<int> ids;
    int n, m, k;
    cin>>n>>m>>k;
    vector<lint> cost(m-1 + n + m-1);
    for(int i = m-1; i < m-1 + n; i++){
        ids.insert(i);
        cin>>cost[i];
    }
    FT<lint> ft(cost.size());
    for(int i =m; i <= (int) cost.size(); i++){
        lint val = ft.query(i - m, i);
        while(val < k){
            if(ids.empty()) break;
            auto it = ids.lower_bound(i);
            if(it == ids.begin()) break;
            it--;
            int j = *it;
            if(j < i - m) break;
            lint dif = k - val;

            lint cur = min(dif, cost[j]);

            cost[j] -= cur;
            ft.update(j, cur);
            if(cost[j] == 0){
                ids.erase(j);
            }
            val = ft.query(i - m, i);
        }
    }
    cout<<ft.query(0, (int) cost.size())<<"\n";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3472kb

input:

8 3 2
3
1
4
1
5
9
2
6

output:

8

result:

ok single line: '8'

Test #2:

score: 0
Accepted
time: 55ms
memory: 15676kb

input:

200000 2467 999931035
182548858
69876218
33328350
919486767
739850600
948199964
392292320
39077742
366752074
917496841
246661698
37219034
56677740
188278971
965701828
28059790
13200243
825730775
542597589
320715170
939054378
470563899
914247467
990100491
290827128
903662394
611104879
18631185
412134...

output:

82994275905

result:

ok single line: '82994275905'

Test #3:

score: 0
Accepted
time: 1ms
memory: 9260kb

input:

1 200000 999959273
1255319

output:

1255319

result:

ok single line: '1255319'

Test #4:

score: 0
Accepted
time: 56ms
memory: 19272kb

input:

200000 118880 996878327
993340390
999483057
808153702
337349872
863222189
7495963
995920883
12950768
958082368
993215196
967152406
1388062
949959944
836952150
964071667
5291
139115263
958470154
51295691
175385
925242139
995685554
10895812
12563
55482
479983443
42805
996241239
6228013
302633329
10331...

output:

2990634981

result:

ok single line: '2990634981'

Test #5:

score: 0
Accepted
time: 73ms
memory: 15744kb

input:

200000 15 44049967
999927791
29351
999894087
687373343
518282902
19725626
452930
6701
999697321
27032796
5498
259987
999999980
485673990
805879
315651507
166801295
189865616
999910671
6203805
978801777
41916529
942904087
997589912
17146790
922137016
444882952
999884603
999926345
938979650
18597283
9...

output:

598769574112

result:

ok single line: '598769574112'