QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129428 | #6136. Airdrop | Energy_is_not_over# | WA | 255ms | 8064kb | C++17 | 4.2kb | 2023-07-22 19:26:00 | 2023-07-22 19:26:01 |
Judging History
answer
//
// Created by Barichek on 22.07.2023 14:00:51
//
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = 1e5+10, inf = 1000111222;
int have[2*max_n];
int T;
void solve()
{
int n,y0;
cin>>n>>y0;
y0++;
vector<pii> xy(n);
for (int i=0;i<n;i++){
cin>>xy[i].fir>>xy[i].sec;
xy[i].fir++;
xy[i].sec++;
}
vector<int> Xs;
for (auto i:xy){
Xs.pb(i.fir-1);
Xs.pb(i.fir);
Xs.pb(i.fir+1);
}
sort(all(Xs));
Xs.resize(unique(all(Xs))-Xs.begin());
vector<int> ans(len(Xs),0);
DEBUG{
for (auto i:Xs){
cerr<<i<<" ";
}
cerr<<"\n";
};
for (int i=0;i<len(Xs);i++){
// LOG(i,ans[i]);
// LOG(i,Xs[i],lower_bound(all(xy),mp(Xs[i],+inf))-lower_bound(all(xy),mp(Xs[i]-1,+inf)));
ans[i]+=lower_bound(all(xy),mp(Xs[i],+inf))-lower_bound(all(xy),mp(Xs[i]-1,+inf));
}
DEBUG{
cerr<<"after base ans :: ";
for (int i=0;i<len(Xs);i++){
cerr<<Xs[i]<<" "<<ans[i]<<", ";
}
cerr<<"\n";
};
{
T++;
int cnt_have_equal_T=0;
int p=0;
for (int X_id=0;X_id<len(Xs);X_id++){
const int X=Xs[X_id];
int r_p=p;
while (r_p<len(xy) && xy[r_p].fir<X){
r_p++;
}
for (int i=p;i<r_p;i++){
int val=max_n-xy[i].fir+abs(y0-xy[i].sec);
if (have[val]<T){
have[val]=T;
cnt_have_equal_T++;
}
else{
cnt_have_equal_T-=(have[val]==T);
have[val]=T+1;
}
}
for (int i=p;i<r_p;i++){
int val=max_n-xy[i].fir+abs(y0-xy[i].sec);
if (have[val]==T+1){
have[val]=-1;
}
}
ans[X_id]+=cnt_have_equal_T;
p=r_p;
}
}
DEBUG{
cerr<<"after left ans :: ";
for (int i=0;i<len(Xs);i++){
cerr<<Xs[i]<<" "<<ans[i]<<", ";
}
cerr<<"\n";
};
{
T++;
int cnt_have_equal_T=0;
int p=len(xy)-1;
for (int X_id=len(Xs)-1;X_id>=0;X_id--){
const int X=Xs[X_id];
int r_p=p;
while (r_p>=0 && xy[r_p].fir>X){
r_p--;
}
for (int i=p;i>r_p;i--){
int val=xy[i].fir+abs(y0-xy[i].sec);
if (have[val]<T){
have[val]=T;
cnt_have_equal_T++;
}
else{
cnt_have_equal_T-=(have[val]==T);
have[val]=T+1;
}
}
for (int i=p;i>r_p;i--){
int val=xy[i].fir+abs(y0-xy[i].sec);
if (have[val]==T+1){
have[val]=-1;
}
}
ans[X_id]+=cnt_have_equal_T;
p=r_p;
}
}
DEBUG{
cerr<<"after right ans :: ";
for (int i=0;i<len(Xs);i++){
cerr<<Xs[i]<<" "<<ans[i]<<", ";
}
cerr<<"\n";
};
cout<<*min_element(all(ans))<<" "<<*max_element(all(ans))<<"\n";
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int tests;
cin>>tests;
while (tests--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
input:
3 3 2 1 2 2 1 3 5 3 3 2 1 2 5 4 3 2 3 1 3 4 3
output:
1 3 0 3 2 2
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 255ms
memory: 8064kb
input:
3508 6 1 7 1 1 1 9 1 10 1 3 1 4 1 3 8 8 9 8 7 1 8 9 5 10 1 10 8 10 2 5 1 9 9 5 9 10 9 6 4 4 7 6 7 10 5 3 8 9 5 9 9 7 5 4 7 10 5 6 9 9 5 6 6 9 3 3 2 5 1 3 8 6 4 5 9 10 2 2 9 10 10 10 8 4 1 7 1 6 1 3 1 5 1 2 4 9 3 3 3 4 5 3 8 9 6 9 9 6 3 9 5 9 3 2 9 9 1 9 2 4 1 5 4 5 6 6 5 9 8 4 1 2 1 5 1 7 1 3 1 9 10...
output:
0 6 0 3 0 9 0 4 1 10 0 2 0 4 0 2 1 4 1 4 1 4 2 9 0 6 0 7 1 8 0 2 0 6 4 10 1 9 1 3 2 4 0 2 2 4 1 7 2 6 1 9 2 2 0 2 1 5 0 6 2 2 1 1 1 5 0 6 3 8 1 1 0 7 2 5 0 7 0 2 0 7 1 1 0 6 1 4 0 6 0 6 0 6 0 2 0 9 0 6 1 1 2 8 2 2 2 2 0 9 2 9 0 6 0 4 1 5 0 2 1 4 0 3 0 5 0 4 1 4 2 2 2 6 2 6 0 6 0 2 0 6 0 4 1 8 0 5 1 ...
result:
wrong answer 1st numbers differ - expected: '6', found: '0'