QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#24672#1877. Matryoshka Dollszzy0922WA 24ms17216kbC++2.6kb2022-04-02 08:16:022022-04-30 06:26:30

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 06:26:30]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:17216kb
  • [2022-04-02 08:16:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21],*p1 = buf,*p2 = buf;
inline int read()
{
    char c = getchar();
    int x = 0;
    bool f = 0;
    for(;!isdigit(c); c = getchar()) f ^= !(c ^ 45);
    for(;isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    if (f) x = -x; 
    return x;
}

int n, m, a[500005], b[500005], pos[500005];
long long anslist[500005];
int len;
struct query{
    int l, r, idx;
    bool operator<(query a) {
        if (l / len == a.l / len) return r > a.r;
        else return l / len < a.l / len; 
    }
}q[500005];

struct node {
    int val, next, prev;
}lis[500005];
#define head lis[0]
#define tail lis[n + 1]
long long ans, tmp, now;

void del(int p, long long& x) {
    if (lis[p].prev == 0) x -= abs(p - lis[p].next);
    else if (lis[p].next == n + 1) x -= abs(p - lis[p].prev);
    else if (lis[p].prev == 0 && lis[p].next == n + 1) x = 0;
    else x = x - abs(p - lis[p].prev) - abs(p - lis[p].next) + abs(lis[p].next - lis[p].prev);
    lis[lis[p].prev].next = lis[p].next;
    lis[lis[p].next].prev = lis[p].prev;
}

void rcv(int p) {
    lis[lis[p].prev].next = p;
    lis[lis[p].next].prev = p;
}

int main() {
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        lis[i].val = a[i];
    for (int i = 1; i <= n; i++)
        pos[a[i]] = i;
    memcpy(b, a, sizeof a);
    sort(b + 1, b + n + 1);
    for (int i = 1; i < n; i++) {
        ans += abs(pos[b[i]] - pos[b[i + 1]]);
    }
    head.next = pos[b[1]];
    lis[pos[b[1]]].prev = 0;
    for (int i = 1; i < n; i++) {
        lis[pos[b[i]]].next = pos[b[i + 1]];
        lis[pos[b[i + 1]]].prev = pos[b[i]];
    }
    tail.prev = pos[b[n]];
    lis[pos[b[n]]].next = n + 1;
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &q[i].l, &q[i].r);
    for (int i = 1; i <= m; i++)
        q[i].idx = i;
    sort (q + 1, q + m + 1);
    now = ans;
    //cout << ans;
    for (int i = 1, l = 1, r = n; i <= m; i++) {
        if (q[i].l / len != q[i - 1].l /len) {
            while (l < (q[i].l - 1) / len * len + 1) del(l++, now);
            r = n;
            tmp = ans = now;
        }
        while (r > q[i].r) del(r--, ans);
        tmp = ans;
        while (l < q[i].l) del(l++, tmp);
        anslist[q[i].idx] = tmp;
        while (l > (q[i].l - 1) / len * len + 1) rcv(l--);
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", anslist[i]);
    return 0;
}

詳細信息

Test #1:

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

input:

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

output:

7
5
3
1
0

result:

ok 5 number(s): "7 5 3 1 0"

Test #2:

score: 0
Accepted
time: 2ms
memory: 16004kb

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 24ms
memory: 17216kb

input:

100000 1
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...

output:

4999950000

result:

ok 1 number(s): "4999950000"

Test #4:

score: 0
Accepted
time: 2ms
memory: 13952kb

input:

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

output:

36

result:

ok 1 number(s): "36"

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 15980kb

input:

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

output:

18
39
57
18
20
4
8
47
3
-15

result:

wrong answer 1st numbers differ - expected: '7', found: '18'