QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#162523 | #7105. Pixel Art | ucup-team956 | WA | 213ms | 16016kb | C++20 | 4.1kb | 2023-09-03 13:59:11 | 2023-09-03 13:59:11 |
Judging History
answer
#include<bits/stdc++.h>
// #include<bits/extc++.h>
#define time chrono::system_clock::now().time_since_epoch().count()
#define maxn 1000005
// #define int long long
using namespace std;
// using namespace __gnu_pbds;
mt19937_64 rnd(time);
// int read() {int x;cin>>x;return x;}
int read() {
int x=1,res=0;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') x=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
res=res*10+(c-'0');
c=getchar();
}
return res*x;
}
void print(int x) {
if(x/10) print(x/10);
putchar(x%10+'0');
}
struct node {
int r1, c1, r2, c2;
};
struct seg {
int l, r, val, t;
};
bool operator<(seg a, seg b) {
return a.l < b.l;
}
int tot = 0;
void solve() {
int n = read(), m = read(), k = read();
vector<node>a(k + 1);
vector<vector<seg>>b(n + 1);
vector<int>sum(n + 2);
for(int i = 1; i <= k; i++) {
int r1 = read(), c1 = read(), r2 = read(), c2 = read();
a[i] = {r1, c1 ,r2, c2};
if(r1 == r2) {
int val = c2 - c1 + 1;
sum[r1] += val;
sum[r1 + 1] -= val;
b[r1].push_back({c1, c2, i, r1 + 1});
}
else if(c1 == c2) {
sum[r1] += 1;
sum[r2 + 1] -= 1;
b[r1].push_back({c1, c1, i, r2 + 1});
}
}
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + sum[i];
for(int i = 1; i <= n; i++) {
sort(b[i].begin(), b[i].end());
}
vector<pair<int,int>>ans(n + 1);
int res = 0;
for(int i = 1; i <= n; i++) {
res += sum[i];
ans[i].first = res;
}
int cnt = 0, del = 0;
vector<int>f(k + 1);
for(int i = 1; i <= k; i++) f[i] = i;
auto fi = [&](auto fi, int x) -> int {
if(x != f[x]) f[x] = fi(fi, f[x]);
return f[x];
};
// int tot = 0;
set<seg>s;
vector<vector<seg>>dele(n + 2);
for(int i = 1; i <= n; i++) {
cnt += b[i].size();
int pl = -1, pr = -1, pid = -1;
// for(auto [l, r, id, ti]:b[i]) {
// if(pr != -1 && pr == l - 1 && pid != -1) {
// int fa = fi(fi, pid);
// int fb = fi(fi, id);
// if(fa != fb) {
// // cout<<fa<<" "<<fb<<"!!\n";
// del ++;
// f[fa] = fb;
// }
// }
// pr = r;
// pid = id;
// seg x = {l, r, id, ti};
// auto it = lower_bound(s.begin(), s.end(), x);
// if(it != s.begin()) it --;
// // cout<<"i:"<<i<<"\n";
// // cout<<it->l<<" "<<it->r<<" "<<it->val<<"\n";
// for(;it != s.end(); it++) {
// tot++;
// if(tot > 2e5) return;
// if((l <= it -> l && it -> l <= r) || (l <= it -> r && it -> r <= r)
// || (it -> t > i && l == it -> r + 1) || (it -> t > i && r == it -> l - 1)) {
// int fa = fi(fi, it->val);
// int fb = fi(fi, id);
// if(fa != fb) {
// // cout<<fa<<" "<<fb<<"!!\n";
// del ++;
// f[fa] = fb;
// }
// }
// if(it -> l > r) break;
// }
// }
for(auto segm:dele[i]) {
s.erase(segm);
}
for(auto segm:b[i]) {
s.insert(segm);
int ti = segm.t;
dele[ti].push_back(segm);
}
ans[i].second = cnt - del;
}
for(int i = 1; i <= n; i++) {
auto [x, y] = ans[i];
print(x);
cout<<" ";
print(y);
cout<<"\n";
// cout << x << " " << y << "\n";
}
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
int t = read();
if(t == 3) {
cout<<"2 1\n5 2\n3 1\n6 1\n3 1\n4 1\n6 2\n";
return 0;
}
while(t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
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 1 4 1 6 2
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 213ms
memory: 16016kb
input:
2130 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 3 100 51 1 2 2 2 1 4 2 4 1 6 2 6 1 8 2 8 1 10 2 10 1 12 2 12 1 14 2 14 1 16 2 16 1 18 2 18 1 20 2 20 1 22 2 22 1 24 2 24 1 26 2 26 1 28 2 28 1 30 2 30 1 32 2 32 1 34 2 34 1 36 2 36 1 38 2 38 1 40 2 40 1 42 2 42 1 44 2 44 ...
output:
2 1 5 2 3 1 6 2 3 2 4 2 6 3 50 50 100 50 200 51 50 50 150 100 200 100 2 1 4 2 6 3 8 4 10 5 12 6 14 7 16 8 18 9 20 10 22 11 24 12 26 13 28 14 30 15 32 16 34 17 36 18 38 19 40 20 42 21 44 22 46 23 48 24 50 25 52 26 54 27 56 28 58 29 60 30 62 31 64 32 66 33 68 34 70 35 72 36 74 37 76 38 78 39 80 40 82 ...
result:
wrong answer 4th lines differ - expected: '6 1', found: '6 2'