QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #19025 | #1877. Matryoshka Dolls | BrotherCall | TL | 27ms | 12524kb | C++14 | 3.4kb | 2022-01-27 18:52:02 | 2022-05-06 03:36:45 |
Judging History
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];
long long 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++) {
//cout<<G[i].x<<' '<<G[i].y<<endl;
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));
}
//cout<<1<<' '<<l<<' '<<r<<' '<<ans<<endl;
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 --;
}
//cout<<2<<' '<<l<<' '<<r<<' '<<ans<<endl;
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 ++;
}
//cout<<3<<' '<<l<<' '<<r<<' '<<ans<<endl;
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));
}
//cout<<4<<' '<<l<<' '<<r<<' '<<ans<<endl;
fans[G[i].seat] = ans;
}
for(int i=1;i<=m;i++)
printf("%lld\n" , fans[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7836kb
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: 7820kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 27ms
memory: 12524kb
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: 1ms
memory: 7824kb
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
Time Limit Exceeded
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