QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#264282 | #3310. Steel Slicing 2 | lmeowdn | WA | 3ms | 21504kb | C++14 | 2.0kb | 2023-11-25 13:31:11 | 2023-11-25 13:31:11 |
Judging History
answer
//vanitas vanitatum et omnia vanitas
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=5e5+5;
int n,a[N],b[N],ans;
vi p[N];
void work(int *a) {
static int st[N]; int top=0;
rep(i,2,n) ans+=(a[i]!=a[i-1]);
rep(i,1,n) {
while(top&&a[st[top]]>a[i]) --top;
if(a[st[top]]==a[i]) {
if(st[top]!=i-1) p[st[top]+1].eb(i), --ans;
st[top]=i;
} else st[++top]=i;
}
}
signed main() {
n=read();
rep(i,1,n) a[i]=read(), b[i]=read();
work(a), work(b);
int X=1; priority_queue<int> q;
rep(i,2,n) if(a[i]!=a[i-1]&&b[i]!=b[i-1]) {
--ans;
while(X<i) {++X; for(int r:p[X]) q.push(r);}
while(!q.empty()&&q.top()<i) q.pop();
if(!q.empty()) q.pop(), ++ans;
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 21304kb
input:
8 1 4 4 2 3 2 5 1 6 4 4 2 2 3 5 1
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 3ms
memory: 20944kb
input:
5 23 15 23 17 3 22 15 3 5 1
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 21212kb
input:
8 1 2 2 2 2 1 1 1 1 2 2 2 2 2 1 2
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 2ms
memory: 20628kb
input:
2 1 1000000 1000000 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 21228kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 3ms
memory: 21504kb
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0
result:
ok single line: '0'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 19832kb
input:
1000 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1 1 2 1 2 1 1 1 2 2 1 1 1 1 2 2 2 1 1 2 2 1 2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 2 1 2 2 1 2 2 1 1 2 1 2 2 2 1 2 1 2 2 2 2 1 2 1 2 1 1 2 2 1 2 2 1 1 1 2 2 2 2 1 1 1 1 1 2 1 2 2 2 2 1 1 1 1 1 1 1 1 2 1 2 2 1 2 2 1 2 2 1 1 2 2 2 1 2 1 1 1 2 1 2 1 2 1 1 2 1 1 2 1 2 1 2 1 2 2...
output:
504
result:
wrong answer 1st lines differ - expected: '505', found: '504'