QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #159615 | #7105. Pixel Art | ucup-team296# | TL | 1ms | 3664kb | C++14 | 8.0kb | 2023-09-02 18:10:57 | 2023-09-02 18:10:57 |
Judging History
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct Dsu {
vector<int> p;
Dsu(int n) {
p.resize(n);
for (int i = 0; i < n; i++) p[i] = i;
}
int get(int x) {
if (p[x] != x) p[x] = get(p[x]);
return p[x];
}
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return false;
p[x] = y;
return true;
}
};
struct test {
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> x1(k), x2(k), y1(k), y2(k);
for (int i = 0; i < k; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i]--, x2[i]--, y1[i]--, y2[i]--;
}
vector<long> res1(n + 1);
{
for (int i = 0; i < k; i++) {
int d = y2[i] - y1[i] + 1;
res1[x1[i]] += d;
res1[x2[i] + 1] -= d;
}
for (int i = 1; i <= n; i++) {
res1[i] += res1[i - 1];
}
for (int i = 1; i <= n; i++) {
res1[i] += res1[i - 1];
}
}
vector<long> res2(n + 1);
for (int i = 0; i < k; i++) {
res2[x1[i]]++;
}
vector<vector<pair<int, int>>> e(n + 1);
{
vector<set<pair<int, int>>> xx(n);
for (int i = 0; i < k; i++) {
if (y1[i] == y2[i]) {
xx[x1[i]].insert({y1[i], i});
xx[x2[i]].insert({y2[i], i});
}
}
for (int i = 0; i < k; i++) {
if (x1[i] == x2[i]) {
int x = x1[i];
if (x > 0) {
int yy = y1[i];
while (true) {
auto p = xx[x - 1].find({yy, 0});
if (p == xx[x - 1].end() || p->first > y2[i]) break;
e[x].push_back({i, p->second});
yy = p->first + 1;
}
}
if (x < n - 1) {
int yy = y1[i];
while (true) {
auto p = xx[x + 1].find({yy, 0});
if (p == xx[x + 1].end() || p->first > y2[i]) break;
e[x + 1].push_back({i, p->second});
yy = p->first + 1;
}
}
}
}
}
{
vector<set<pair<int, int>>> yy(m);
for (int i = 0; i < k; i++) {
if (x1[i] == x2[i]) {
yy[y1[i]].insert({x1[i], i});
yy[y2[i]].insert({x2[i], i});
}
}
for (int i = 0; i < k; i++) {
if (y1[i] == y2[i]) {
int y = y1[i];
if (y > 0) {
int xx = x1[i];
while (true) {
auto p = yy[y - 1].find({xx, 0});
if (p == yy[y - 1].end() || p->first > x2[i]) break;
e[p->first].push_back({i, p->second});
xx = p->first + 1;
}
}
if (y < m - 1) {
int xx = x1[i];
while (true) {
auto p = yy[y + 1].find({xx, 0});
if (p == yy[y + 1].end() || p->first > x2[i]) break;
e[p->first].push_back({i, p->second});
xx = p->first + 1;
}
}
}
}
}
{
vector<vector<int>> s(n);
for (int i = 0; i < k; i++) {
if (x1[i] == x2[i]) {
s[x1[i]].push_back(i);
}
}
for (int i = 0; i < n; i++) {
vector<pair<int, int>> ee;
for (int j: s[i]) {
ee.push_back({y1[j], j});
ee.push_back({y2[j], j});
}
sort(ee.begin(), ee.end());
int kk = ee.size();
for (int j = 0; j < kk - 1; j++) {
if (ee[j].first == ee[j + 1].first - 1) {
e[i].push_back({ee[j].second, ee[j + 1].second});
}
}
}
for (int i = 0; i < n - 1; i++) {
vector<pair<int, int>> ee;
for (int j : s[i]) {
ee.push_back({y1[j], j + 1});
ee.push_back({y2[j] + 1, -j - 1});
}
for (int j : s[i + 1]) {
ee.push_back({y1[j], j + 1});
ee.push_back({y2[j] + 1, -j - 1});
}
sort(ee.begin(), ee.end());
int cn = 0;
int cs = 0;
for (auto p : ee) {
if (p.second > 0) {
if (cn == 1) {
e[i + 1].push_back({p.second - 1, cs});
}
cn++;
cs += p.second - 1;
} else {
cn--;
cs -= (-p.second - 1);
}
}
}
}
{
vector<vector<int>> s(m);
for (int i = 0; i < k; i++) {
if (y1[i] == y2[i]) {
s[y1[i]].push_back(i);
}
}
for (int i = 0; i < m; i++) {
vector<pair<int, int>> ee;
for (int j: s[i]) {
ee.push_back({x1[j], j});
ee.push_back({x2[j], j});
}
sort(ee.begin(), ee.end());
int kk = ee.size();
for (int j = 0; j < kk - 1; j++) {
if (ee[j].first == ee[j + 1].first - 1) {
e[ee[j].first + 1].push_back({ee[j].second, ee[j + 1].second});
}
}
}
for (int i = 0; i < m - 1; i++) {
vector<pair<int, int>> ee;
for (int j : s[i]) {
ee.push_back({x1[j], j + 1});
ee.push_back({x2[j] + 1, -j - 1});
}
for (int j : s[i + 1]) {
ee.push_back({x1[j], j + 1});
ee.push_back({x2[j] + 1, -j - 1});
}
sort(ee.begin(), ee.end());
int cn = 0;
int cs = 0;
for (auto p : ee) {
if (p.second > 0) {
if (cn == 1) {
e[max(x1[cs], x1[p.second - 1])].push_back({p.second - 1, cs});
}
cn++;
cs += p.second - 1;
} else {
cn--;
cs -= (-p.second - 1);
}
}
}
}
Dsu dsu(k);
for (int i = 0; i < n; i++) {
for (auto [x, y]: e[i]) {
if (dsu.unite(x, y)) {
res2[i]--;
}
}
}
for (int i = 1; i <= n; i++) {
res2[i] += res2[i - 1];
}
for (int i = 0; i < n; i++) {
cout << res1[i] << " " << res2[i] << "\n";
}
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
test().solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
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
Time Limit Exceeded
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 1 3 1 4 1 6 2 50 50 100 50 200 51 50 50 150 1 200 1 2 1 4 1 6 1 8 1 10 1 12 1 14 1 16 1 18 1 20 1 22 1 24 1 26 1 28 1 30 1 32 1 34 1 36 1 38 1 40 1 42 1 44 1 46 1 48 1 50 1 52 1 54 1 56 1 58 1 60 1 62 1 64 1 66 1 68 1 70 1 72 1 74 1 76 1 78 1 80 1 82 1 84 1 86 1 88 1 90 1 92 1 94 1 96 ...