QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385642#5102. Dungeon CrawlerSolitaryDream#WA 1ms7720kbC++174.1kb2024-04-10 22:30:042024-04-10 22:30:05

Judging History

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

  • [2024-04-10 22:30:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7720kb
  • [2024-04-10 22:30:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 8e5 + 10;
int n, m, s;
namespace Seg {
    int L[N], R[N], tg[N];
    inline void SetTag(int v, int z) {
        tg[v] += z;
        L[v] += z;
        R[v] += z;
    }
    inline void PushDown(int v) {
        if (tg[v]) {
            SetTag(v << 1, tg[v]);
            SetTag(v << 1 | 1, tg[v]);
            tg[v] = 0;
        }
    }
    inline void PushUp(int v) {
        L[v] = L[v << 1];
        R[v] = R[v << 1 | 1];
    }
    inline void Init(int v = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            int d1 = (s - l + n) % n;
            int d2 = (l - s + n) % n;
            L[v] = R[v] = min(d1, d2);
            return;
        }
        int mid = (l + r) >> 1;
        Init(v << 1, l, mid); Init(v << 1 | 1, mid + 1, r);
        PushUp(v);
    }
    inline int Ask(int x, int v = 1, int l = 0, int r = n - 1) {
        if (l == r) return L[v];
        int mid = (l + r) >> 1;
        PushDown(v);
        return x <= mid ? Ask(x, v << 1, l, mid) : Ask(x, v << 1 | 1, mid + 1, r);
    }
    inline void Set(int x, int z, int v = 1, int l = 0, int r = n - 1) {
        if (l == r) { L[v] = R[v] = z; return; }
        int mid = (l + r) >> 1;
        PushDown(v);
        if (x <= mid) Set(x, z, v << 1, l, mid); else Set(x, z, v << 1 | 1, mid + 1, r);
        PushUp(v);
    }
    inline void Add(int x, int y, int z, int v, int l, int r) {
        if (x > r || y < l) return;
        if (x <= l && r <= y) { SetTag(v, z); return; }
        int mid = (l + r) >> 1;
        PushDown(v);
        Add(x, y, z, v << 1, l, mid); Add(x, y, z, v << 1 | 1, mid + 1, r);
        PushUp(v);
    }
    inline void UpdateInc(int x, int z, int v = 1, int l = 0, int r = n - 1) {  // x..n-1
        if (l == r) { 
            if (l >= x) L[v] = R[v] = min(L[v], z + (l - x));
            return;
        }
        int mid = (l + r) >> 1;
        PushDown(v);
        if (mid <= x) UpdateInc(x, z, v << 1 | 1, mid + 1, r);
        else {
            int vl = L[v << 1 | 1];
            if (vl <= z + (mid + 1 - x)) UpdateInc(x, z, v << 1, l, mid);
            else { Add(x, n - 1, -1, v << 1, l, mid); UpdateInc(x, z, v << 1 | 1, mid + 1, r); }
        }
        PushUp(v);
    }
   inline void UpdateDec(int x, int z, int v = 1, int l = 0, int r = n - 1) {  // 0..x
        if (l == r) { 
            if (l <= x) L[v] = R[v] = min(L[v], z + (x - l));
            return;
        }
        int mid = (l + r) >> 1;
        PushDown(v);
        if (mid + 1 > x) UpdateDec(x, z, v << 1, l, mid);
        else {
            int vr = R[v << 1];
            if (vr <= z + (x - mid)) UpdateDec(x, z, v << 1 | 1, mid + 1, r);
            else { Add(0, x, -1, v << 1 | 1, mid + 1, r); UpdateDec(x, z, v << 1, l, mid); }
        }
        PushUp(v);
    }
    inline void PrintAns(int v = 1, int l = 0, int r = n - 1) {
        if (l == r) { cout << L[v] << '\n'; return; }
        int mid = (l + r) >> 1;
        PushDown(v);
        PrintAns(v << 1, l, mid); PrintAns(v << 1 | 1, mid + 1, r);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s;
    --s;
    vector<pii> ops;
    for (int i = 1, x, y; i <= m; ++i) {
        cin >> x >> y;
        --y;
        ops.push_back({x, y});
    }
    sort(ops.begin(), ops.end(), greater<pii>());
    Seg::Init();
    for (auto [_x, pb] : ops) {
        Seg::PrintAns();
        cout << endl;
        int pa = (pb + n - 1) % n, pc = (pb + 1) % n, pd = (pc + 1) % n;
        int vb = Seg::Ask(pb), vc = Seg::Ask(pc);
        if (vb == vc) {
            // pass
        } else if (vb > vc) {
            Seg::Set(pc, min(vb, Seg::Ask(pd) + 1));
            // a[pb] = vc
            Seg::UpdateDec(pb, vc);
            Seg::UpdateDec(n - 1, vc + pb + 1);
        } else {
            Seg::Set(pb, min(vc, Seg::Ask(pa) + 1));
            // a[pc] = vb;
            Seg::UpdateInc(pc, vb);
            Seg::UpdateInc(0, vb + n - pc);
        }
    }
    Seg::PrintAns();
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7720kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

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

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

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

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

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

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

result:

wrong answer 1st lines differ - expected: '316', found: '0'