QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644475#9409. SensorspropaneAC ✓1861ms166300kbC++202.9kb2024-10-16 14:09:252024-10-16 14:09:26

Judging History

This is the latest submission verdict.

  • [2024-10-16 14:09:26]
  • Judged
  • Verdict: AC
  • Time: 1861ms
  • Memory: 166300kb
  • [2024-10-16 14:09:25]
  • Submitted

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<array>
#include<map>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 5e5 + 5;
vector<pair<int, int> > s[maxn * 4];
int x[maxn], y[maxn];

void insert(int u, int l, int r, int id){
    s[u].push_back({y[id], id});
    if (l == r) return;
    int mid = (l + r) / 2;
    if (x[id] <= mid) insert(2 * u, l, mid, id);
    else insert(2 * u + 1, mid + 1, r, id);
}

vector<int> p;

bool del[maxn];

void query(int u, int l, int r, int L, int R, int ll, int rr){
    if (l > R or r < L) return;
    if (l >= L and r <= R){
        while(!s[u].empty()){
            if (del[s[u].back().second]){
                s[u].pop_back();
            }
            else if (s[u].back().first <= rr){
                del[s[u].back().second] = true;
                p.push_back(s[u].back().second);
                s[u].pop_back();
            }
            else break;
        }
        return;
    }
    int mid = (l + r) / 2;
    query(2 * u, l, mid, L, R, ll, rr);
    query(2 * u + 1, mid + 1, r, L, R, ll, rr);
}


int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;

        for(int i = 1; i <= 4 * n; i++){
            s[i].clear();
        }

        LL ans = 0;
        vector<LL> mp(n + 1);
        for(int i = 1; i <= m; i++){
            del[i] = false;
            cin >> x[i] >> y[i];
            x[i] += 1, y[i] += 1;
            if (y[i] - x[i] + 1 == 1){
                ans += 1LL * i * i;
                mp[x[i]] += 1LL * i * i;
            }
            else{
                insert(1, 1, n, i);
            }
        }

        for(int i = 1; i <= 4 * n; i++){
            sort(s[i].begin(), s[i].end(), greater<>());
        }

        set<int> s0;
        for(int i = 0; i <= n + 1; i++) s0.insert(i);

        auto solve = [&](int x){
            if (x < 1 or x > n) return;
            auto it = s0.lower_bound(x);
            int pre = *prev(it) + 1;
            int nxt = *next(it) - 1;
            // [pre, x], [x, nxt]
            p.clear();
            query(1, 1, n, pre, x, x, nxt);
            for(auto id : p){
                ans += 1LL * id * id;
                mp[x] += 1LL * id * id;
            }
        };

        cout << ans << ' ';
        for(int i = 0; i < n; i++){
            int x;
            cin >> x;
            x = (x + ans) % n + 1;
            ans -= mp[x];
            s0.erase(x);
            auto it = s0.lower_bound(x);
            solve(*prev(it));
            solve(*it);
            cout << ans << ' ';
        }
        cout << '\n';
    }

}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5524kb

input:

3
5 4
2 4
2 3
3 3
0 2
3 2 4 2 0
2 1
1 1
1 0
2 1
0 1
0 0

output:

9 13 29 17 16 0 
1 1 0 
0 1 0 

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 664ms
memory: 38132kb

input:

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

output:

133 220 0 
0 0 1 0 
0 0 0 0 4 4 5 4 0 
0 4 4 4 4 5 0 
91 0 
0 0 0 0 1 0 
13 13 4 0 1 0 
168 249 105 135 136 0 
0 4 13 9 0 0 16 17 0 
79 127 0 
1 54 0 
0 0 25 25 25 61 40 57 21 14 0 
385 0 
0 0 9 71 9 53 69 0 
0 0 9 9 9 46 0 
35 39 203 0 
1 10 9 9 9 54 0 
5 5 5 0 0 
5 13 13 4 16 16 16 0 
4 4 5 5 5 4 ...

result:

ok 2227 lines

Test #3:

score: 0
Accepted
time: 1861ms
memory: 166300kb

input:

1
500000 500000
369902 382967
262235 295509
296241 456925
21398 104992
37225 97384
380549 388723
338331 494405
150247 262207
70049 286642
214690 432702
268101 392964
99683 217894
89569 351594
126467 380939
152103 169827
171887 422097
166531 416410
44667 160325
210347 371355
47557 119914
74437 200422...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...9642788310 20801182804434259 0 '

Test #4:

score: 0
Accepted
time: 964ms
memory: 113144kb

input:

1
500000 500000
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499999
0 499...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 41666791666750000 0 '

Test #5:

score: 0
Accepted
time: 1008ms
memory: 113184kb

input:

1
500000 500000
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499998
1 499...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 41666791666750000 0 '

Test #6:

score: 0
Accepted
time: 1065ms
memory: 96276kb

input:

1
500000 250000
0 250000
1 250001
2 250002
3 250003
4 250004
5 250005
6 250006
7 250007
8 250008
9 250009
10 250010
11 250011
12 250012
13 250013
14 250014
15 250015
16 250016
17 250017
18 250018
19 250019
20 250020
21 250021
22 250022
23 250023
24 250024
25 250025
26 250026
27 250027
28 250028
29 2...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...18019441588 4838325779633316 0 '

Extra Test:

score: 0
Extra Test Passed