QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#19029	#1877. Matryoshka Dolls	BrotherCall	WA	25ms	12460kb	C++14	3.1kb	2022-01-27 19:16:04	2022-05-06 03:37:16

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-05-06 03:37:16]
评测

测评结果：WA
用时：25ms
内存：12460kb

查看

[2022-01-27 19:16:04]
提交

answer

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#define LL (long long)
using namespace std;

const int N = 5e5 + 100;
int n , m , t;
int a[N];
int fans[N];
struct edge{
    int x , y;
    int seat;
}G[N];
set<pair<int , int> >s;
set<pair<int , int> >::iterator it;
set<pair<int , int> >::iterator it2;
set<pair<int , int> >::iterator it3;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            b=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        a=(a<<3)+(a<<1)+c-'0';
        c=getchar();
    }
    return a*b;
}

bool compare(edge s1 , edge s2) {
    if(s1.x / t == s2.x / t) {
        if((s1.x / t) & 1) return s1.y < s2.y;
            else return s1.y > s2.y;
    }
    return s1.x / t < s2.x / t;
}

int main() {
    n = read() , m = read();
    t = sqrt(n);
    for(int i=1;i<=n;i++)
        a[i] = read();
    for(int i=1;i<=m;i++) {
        G[i].x = read();
        G[i].y = read();
        G[i].seat = i;
    }
    sort(G + 1 , G + 1 + m , compare);
    int l = 1 , r = 0;
    long long ans = 0;
    for(int i=1;i<=m;i++) {
        while(r < G[i].y) {
            r ++;
            s.insert(make_pair(a[r] , r));
            it = s.lower_bound(make_pair(a[r] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans -= LL(abs(it->second - it2->second));
            if(it != s.end()) ans += LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans += LL(abs(it3->second - it2->second));
        }
        while(l > G[i].x) {
            l --;
            s.insert(make_pair(a[l] , l));
            it = s.lower_bound(make_pair(a[l] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans -= LL(abs(it->second - it2->second));
            if(it != s.end()) ans += LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans += LL(abs(it3->second - it2->second));
        }
        while(r > G[i].y) {
            it = s.lower_bound(make_pair(a[r] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans += LL(abs(it->second - it2->second));
            if(it != s.end()) ans -= LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans -= LL(abs(it3->second - it2->second));
            s.erase(it3);
            r --;
        }
        while(l < G[i].x) {
            it = s.lower_bound(make_pair(a[l] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans += LL(abs(it->second - it2->second));
            if(it != s.end()) ans -= LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans -= LL(abs(it3->second - it2->second));
            s.erase(it3);
            l ++;
        }
        fans[G[i].seat] = ans;
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n" , fans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 4ms

memory: 7764kb

input:

output:

result:

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

Test #2:

score: 0

Accepted

time: 0ms

memory: 7800kb

input:

1 1
1
1 1

output:

result:

ok 1 number(s): "0"

Test #3:

score: -100

Wrong Answer

time: 25ms

memory: 12460kb

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:

704982704

result:

wrong answer 1st numbers differ - expected: '4999950000', found: '704982704'