QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#176234 | #7105. Pixel Art | pengpeng_fudan | WA | 2ms | 11140kb | C++17 | 2.2kb | 2023-09-11 12:58:02 | 2023-09-11 12:58:03 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ull=unsigned long long;
using ll=long long;
int n,m,k;
vector<pair<int,int>> ve[100010];
vector<int> hi[100010];
struct seg{
#define ls(x) tr[x].l
#define rs(x) tr[x].r
#define fu(x) tr[x].fu
struct node{
int l,r;bool fu;
}tr[100010*2];
int tot=1;
void clear(int x){ls(x)=rs(x)=fu(x)=0;}
seg(){tot=1,clear(1);}
void clear(){tot=1,clear(1);}
void upd(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){fu(x)=1;return ;}
int mid=(l+r)>>1;
if(mid>=L){
if(!ls(x)){ls(x)=++tot;clear(tot);}
upd(ls(x),l,mid,L,R);
}
if(mid<R){
if(!rs(x)){rs(x)=++tot;clear(tot);}
upd(rs(x),mid+1,r,L,R);
}
}
bool query(int x,int l,int r,int L,int R){
if(fu(x)) return true;
int mid=(l+r)>>1;
bool ans=0;
if(mid>=L&&ls(x)) ans|=query(ls(x),l,mid,L,R);
if(mid<R&&rs(x)) ans|=query(rs(x),mid+1,r,L,R);
return ans;
}
};
seg sg[2];
bool flag[100010];
void solve() {
cin>>n>>m>>k;
fill(flag,flag+m+2,0);
sg[0].clear(),sg[1].clear();
for(int i=1;i<=n;i++){
ve[i].clear();
hi[i].clear();
}
int a,b,c,d;
for(int i=1;i<=k;i++){
cin>>a>>b>>c>>d;
if(a==c) ve[a].push_back({b,d});
else{
hi[a].push_back(b);
hi[c+1].push_back(-b);
}
}
for(int i=1;i<=n;i++) sort(hi[i].begin(),hi[i].end(),[&](int a,int b){if(fabs(a)==fabs(b)) return a<b;else return fabs(a)<fabs(b);});
int black_num=0;
int ltk=0;
int len_num=0;
int t=0;
for(int i=1;i<=n;i++){
t=t^1;
sg[t].clear();
for(auto j:ve[i]) black_num+=j.second-j.first+1;
int sz=hi[i].size();
for(int j=0;j<sz;j++){
int t=hi[i][j];
if(t<0){
flag[j]=0;
len_num--;
}
else{
if(sg[t^1].query(1,1,m,t,t)||flag[t-1]||(j!=0&&hi[i][j-1]==-hi[i][j]));
else ltk++;
flag[j]=1;
len_num++;
}
}
for(auto j:ve[i]){
if(!sg[t^1].query(1,1,m,j.first,j.second)&&!flag[j.first-1]&&!flag[j.second+1]) ltk++;
sg[t].upd(1,1,m,j.first,j.second);
}
black_num+=len_num;
cout<<black_num<<' '<<ltk<<'\n';
}
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0);
int _ = 1;
cin >> _;
while(_--) solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 11140kb
input:
3 2 5 2 1 1 1 2 2 3 2 5 2 5 2 1 1 1 3 2 3 2 5 3 3 3 1 1 1 2 3 1 3 2 1 3 2 3
output:
2 1 5 2 3 1 6 1 3 0 4 0 6 1
result:
wrong answer 5th lines differ - expected: '3 1', found: '3 0'