QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #768271 | #9465. 基础 01 练习题 | peaneval_kala | 0 | 630ms | 139788kb | C++23 | 10.0kb | 2024-11-21 08:08:44 | 2024-11-21 08:08:45 |
Judging History
answer
#pragma GCC optimize(3, "unroll-loops", "no-stack-protector")
#define atsum(l, r) accumulate(l, r, 0)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void chkmin(T &x, T y) { x = min(x, y); }
template <typename T>
inline void chkmax(T &x, T y) { x = max(x, y); }
namespace FastIO
{
// ------------------------------
#define IN_HAS_NEG
#define OUT_HAS_NEG
#define CHK_EOF
#define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined (_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer;
_read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
}
return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c)
{
*_write_ptr++ = c;
if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
{
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
_write_ptr = _write_buffer;
}
}
INLINE_V struct _auto_flush
{
~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
inline bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline bool _isdigit(char c) { return c & 16; }
inline bool _isgraph(char c) { return c > 32; }
#endif
template < class T >
INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
template < class T >
INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T >
INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = gc(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) *s++ = c, c = gc();
*s = 0;
}
inline void read(string &s)
{
char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); bool f = true; x = 0;
while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void read(T &x)
{
char c = gc(); while ( !_isdigit(c) ) c = gc();
x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
while ( digits ) pc(buffer[--digits]);
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
while ( digits ) pc(buffer[--digits]);
}
template < int N > struct _tuple_io_helper
{
template < class ...T >
static inline void _read(tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
};
template <> struct _tuple_io_helper < 1 >
{
template < class ...T >
static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
};
template < class ...T >
inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
template < class ...T >
inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
template < class T1, class T2 >
inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 >
inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
template < class T1, class ...T2 >
inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T >
inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 >
inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T >
inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T >
inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 >
inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template < class ...T >
inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template < class ...T >
inline void println(const T &...x) { print(x...), pc(10); }
template < class ...T >
inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
template <typename T>
inline void clear(T &x) {
T y;
swap(x, y);
}
const int N = 5005, M = 1e4 + 10;
int n, q, type, a[N][N], siz[N], g[N];
int id[N], id2[N], fa[N], mn[N], mx[N], pos[N];
string str[N];
inline int find(int u) { return fa[u] == u ? u : (fa[u] = find(fa[u])); }
priority_queue<int> oc[N];
inline void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
fa[u] = v, chkmin(mn[v], mn[u]), chkmax(mx[v], mx[u]), siz[v] += siz[u];
if (oc[v].size() < oc[u].size()) swap(oc[u], oc[v]);
while (oc[u].size()) oc[v].push(oc[u].top()), oc[u].pop();
g[v] += g[u];
}
int res[N];
int main() {
read(n, q, type);
// assert(type == 0);
for (int i = 1; i <= n; i++) siz[i] = 1, fa[i] = i, mn[i] = mx[i] = i;
while (q--) {
int x1, x2, y1, y2;
read(x1, x2, y1, y2), ++x2, ++y2;
a[x1][y1] ^= 1;
a[x2][y1] ^= 1;
a[x1][y2] ^= 1;
a[x2][y2] ^= 1;
}
for (int i = 1; i <= n; i++) id[i] = id2[i] = i, str[i] = '0';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
a[i][j] = a[i][j] ^ a[i - 1][j] ^ a[i][j - 1] ^ a[i - 1][j - 1];
if (a[i][j]) str[i] += '1';
else str[i] += '0';
}
sort(id + 1, id + n + 1,[&](int x, int y) { return str[x] < str[y]; });
for (int i = 1; i <= n; i++) pos[id2[i]] = i;
for (int i = 1; i <= n; i++) {
int l = inf, r = 0;
for (int j = 1; j <= n; j++)
if (str[id[j]][i] == '1') chkmin(l, j);
else chkmax(r, j);
// cerr << "find youmo:" << l << ' ' << r << endl;
if (l <= r) {
for (int c = l; c <= r; c++) merge(l, c);
int c = find(l);
++g[c];
while (oc[c].size() && oc[c].top() >= mn[c]) ++g[c], oc[c].pop();
} else if (l != inf) oc[find(l)].push(r);
int sg = 0;
ll ans = 1ll * n * i;
// for (int i = 1; i <= n; i++) cerr << find(i) << ' ';
// cerr << endl;
for (int i = 1; i <= n; i++) if (find(i) == i ) {
ll len = g[i] * (mx[i] - mn[i] + 1);
// cerr << "find len:" << len << ' ' << mx[i] << ' ' << mn[i] << endl;
sg += g[i];
ans -= max(len, 1ll);
++ans;
}
write(ans, ' ');
}
return 0;
}
/*
2 2 0
1 1 1 1
2 2 2 2
1 3
2 4
3 2
4 1
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7816kb
input:
4 1000 0 2 3 1 2 1 3 1 3 1 2 1 2 1 2 3 4 1 4 2 4 1 3 1 2 1 4 1 2 1 3 1 4 3 3 2 3 1 2 2 4 4 4 1 3 3 3 3 4 3 4 3 4 2 3 1 1 1 2 2 4 1 4 3 4 3 4 1 2 1 2 2 3 3 4 3 3 1 2 4 4 4 4 2 4 1 4 1 1 1 1 1 3 2 3 2 3 1 1 2 4 2 3 2 4 3 3 1 4 3 3 3 3 1 3 3 3 2 3 2 4 3 3 2 2 1 3 2 4 1 3 1 2 3 4 1 2 2 3 1 3 1 1 1 2 1 2...
output:
4 3 1 1
result:
wrong answer 1st numbers differ - expected: '1', found: '4'
Subtask #2:
score: 0
Wrong Answer
Test #4:
score: 0
Wrong Answer
time: 7ms
memory: 8012kb
input:
50 200000 0 1 45 2 6 29 44 2 6 31 37 2 50 2 37 1 19 7 13 8 38 38 46 19 38 10 30 30 46 22 42 1 45 5 35 24 27 10 36 19 31 20 47 17 35 7 9 23 42 15 26 31 42 7 8 7 42 1 26 33 48 2 5 30 36 17 44 21 44 5 44 24 36 19 47 15 17 29 36 2 42 31 34 11 41 9 24 12 30 30 43 8 20 2 12 13 20 11 12 10 15 14 22 3 29 2 ...
output:
50 61 49 33 21 13 8 9 10 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
result:
wrong answer 1st numbers differ - expected: '1', found: '50'
Subtask #3:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 630ms
memory: 139532kb
input:
5000 200000 0 1438 2561 3478 4930 1740 4634 87 3003 590 3275 1376 1681 2035 2793 2004 4945 567 3159 550 4470 61 3039 3431 3519 2654 3834 3460 4960 591 3560 409 443 345 2599 746 2891 1288 4570 1577 4402 249 377 1951 4534 2411 2455 294 1192 1679 3153 1645 4259 1735 1856 601 668 477 4881 411 2094 424 1...
output:
5000 5851 4543 3369 1996 1285 1023 561 397 341 287 289 287 309 301 321 341 361 115 121 127 89 93 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 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 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '5000'
Subtask #4:
score: 0
Wrong Answer
Test #14:
score: 10
Accepted
time: 615ms
memory: 139356kb
input:
5000 200000 1 565 4401 1659 1826 429 1640 2999 3495 572 3994 9 3863 3844 4284 2307 3144 1054 1943 358 2592 727 4248 29 1171 1685 2392 4559 4929 1149 2787 1204 1947 2349 2619 405 998 1910 2786 25 1275 912 3475 4384 4387 3822 4895 1849 4548 3082 4749 3457 4220 3174 4885 117 1085 2517 3919 4325 4869 17...
output:
5000 5653 3715 1781 1031 823 540 185 190 71 56 61 66 71 76 81 86 91 96 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...
result:
ok 5000 numbers
Test #15:
score: 0
Wrong Answer
time: 350ms
memory: 139788kb
input:
5000 200000 1 1 1 4840 5000 2 2 1690 5000 3 3 908 5000 4 4 1212 5000 5 5 2712 5000 6 6 3950 5000 7 7 4724 5000 8 8 3706 5000 9 9 1888 5000 10 10 4056 5000 11 11 1074 5000 12 12 3806 5000 13 13 3756 5000 14 14 2822 5000 15 15 1264 5000 16 16 4088 5000 17 17 796 5000 18 18 4888 5000 19 19 4610 5000 20...
output:
5000 9997 14997 19997 24997 29994 34974 39958 44944 49928 54902 59872 64858 69833 74833 79777 84760 89728 94710 99675 104675 109599 114599 119536 124492 129423 134374 139298 144270 149188 154130 159041 163948 168851 173814 178678 183638 188563 193522 198522 203288 208204 213158 218030 222898 227719 ...
result:
wrong answer 23rd numbers differ - expected: '114578', found: '114599'
Subtask #5:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
200000 200000 1 1 2 1 6 3 4 1 1 5 6 1 5 7 8 1 3 9 10 1 3 11 12 1 6 13 14 1 5 15 16 1 6 17 18 1 6 19 20 1 1 21 22 1 4 23 24 1 5 25 26 1 2 27 28 1 4 29 30 1 3 31 32 1 2 33 34 1 6 35 36 1 3 37 38 1 2 39 40 1 2 41 42 1 3 43 44 1 1 45 46 1 2 47 48 1 3 49 50 1 4 51 52 1 5 53 54 1 1 55 56 1 5 57 58 1 5 59 ...
output:
result:
Subtask #6:
score: 0
Runtime Error
Test #28:
score: 0
Runtime Error
input:
200000 200000 0 91264 123676 6826 154505 121351 188051 108158 131448 65413 163961 26771 116304 93852 110556 34929 187363 31794 142162 33578 38712 26574 67763 178013 197235 46436 146042 95 122860 11683 50463 60177 195245 60862 194711 37817 97212 144366 176271 113551 171098 120095 170517 73555 167299 ...
output:
result:
Subtask #7:
score: 0
Runtime Error
Test #37:
score: 0
Runtime Error
input:
100000 200000 1 1 22878 1 2 1 7957 3 4 1 21779 5 6 1 34321 7 8 1 41692 9 10 1 49473 11 12 1 10254 13 14 1 43995 15 16 1 46975 17 18 1 668 19 20 1 25996 21 22 1 24975 23 24 1 43259 25 26 1 4174 27 28 1 39330 29 30 1 35462 31 32 1 27523 33 34 1 5574 35 36 1 47955 37 38 1 47013 39 40 1 3846 41 42 1 276...