QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456450 | #210. Terytoria [B] | HaccerKat | 10 ✓ | 2326ms | 93740kb | C++23 | 5.1kb | 2024-06-28 00:44:42 | 2024-06-28 00:44:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
return t.size();
}
template<typename T, size_t N>
int SIZE(T (&t)[N]){
return N;
}
string to_string(char t){
return "'" + string({t}) + "'";
}
string to_string(bool t){
return t ? "true" : "false";
}
string to_string(const string &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += t[i];
}
return '"' + ret + '"';
}
string to_string(const char* t){
string ret(t);
return to_string(ret);
}
template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
ret += t[i] + '0';
}
return to_string(ret);
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);
template<typename T, typename S>
string to_string(const pair<T, S> &t){
return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
string ret = "[";
x1 = min(x1, SIZE(t));
auto e = begin(t);
advance(e,x1);
for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += to_string(*e, C...) + (i != _i ? ", " : "");
e = next(e);
}
return ret + "]";
}
template<int Index, typename... Ts>
struct print_tuple{
string operator() (const tuple<Ts...>& t) {
string ret = print_tuple<Index - 1, Ts...>{}(t);
ret += (Index ? ", " : "");
return ret + to_string(get<Index>(t));
}
};
template<typename... Ts>
struct print_tuple<0, Ts...> {
string operator() (const tuple<Ts...>& t) {
return to_string(get<0>(t));
}
};
template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
const auto Size = tuple_size<tuple<Ts...>>::value;
return print_tuple<Size - 1, Ts...>{}(t);
}
void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
cout << to_string(H) << " | ";
dbgr(T...);
}
void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
cout << H << " ";
dbgs(T...);
}
/*
formatted functions:
*/
/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)
/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
using i128 = __int128;
const int N = 500005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
constexpr ll mod = 345198825136188841;
ll add(ll x, ll y) {
ll res = x + y;
if (res >= mod) res -= mod;
if (res < 0) res += mod;
return res;
}
ll neg(ll x) {
return -x + mod;
}
ll mul(ll x, ll y) {
return (((i128)x * y % mod) + mod) % mod;
}
int n, m, k, qq;
ll solvecoord(vector<pi> a, int X) {
map<ll, int> mp;
vector<pair<int, ll>> pos;
ll curp = 1;
for (int i = 0; i < n; i++) {
auto [l, r] = a[i];
if (l > r) swap(l, r);
pos.push_back({l, add(curp, curp)});
ll y = neg(curp);
pos.push_back({r, add(y, y)});
curp = mul(curp, 4);
}
pos.push_back({0, 0});
pos.push_back({X, 0});
sort(pos.begin(), pos.end());
int sz = pos.size();
ll cur = 0;
for (int i = 1; i < sz; i++) {
auto [p, hash] = pos[i];
auto [pp, hashp] = pos[i - 1];
mp[cur] += p - pp;
cur = add(cur, hash);
}
int mx = 0;
for (auto [hash, cnt] : mp) {
mx = max(mx, cnt);
}
return mx;
}
void solve() {
int X, Y;
cin >> n >> X >> Y;
vector<pi> xx(n), yy(n);
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
xx[i] = {x1, x2}, yy[i] = {y1, y2};
}
ll x = solvecoord(xx, X), y = solvecoord(yy, Y);
cout << x * y << "\n";
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
详细
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 3528kb
input:
8 32 32 17 6 1 24 22 8 29 18 10 21 11 23 2 11 14 13 16 3 22 29 9 15 17 20 12 1 13 28 0 2 3 12
output:
28
result:
ok single line: '28'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
8 32 32 19 22 24 19 5 2 6 3 24 21 22 20 4 7 8 5 26 22 20 20 3 6 8 8 22 22 25 23 8 3 5 4
output:
460
result:
ok single line: '460'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 2 2 1 1 0 0
output:
1
result:
ok single line: '1'
Subtask #2:
score: 1
Accepted
Test #4:
score: 1
Accepted
time: 0ms
memory: 3476kb
input:
100 400 400 18 253 21 63 25 239 340 92 343 333 124 282 184 315 315 215 381 351 386 394 314 19 216 251 184 239 75 236 338 65 200 268 362 290 106 93 294 384 353 301 40 326 334 385 148 94 238 199 146 397 297 98 114 316 97 343 139 93 75 204 235 379 166 183 117 303 213 71 192 100 271 305 88 294 388 215 1...
output:
90
result:
ok single line: '90'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
100 200 200 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
10000
result:
ok single line: '10000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
47 13 29 2 11 11 20 3 24 6 13 3 24 0 7 0 20 3 6 1 4 11 18 7 2 10 21 3 13 1 10 0 22 6 3 11 7 5 18 5 21 12 17 0 25 10 1 4 0 2 4 12 20 7 0 3 1 4 23 12 7 4 0 0 15 1 7 9 20 6 8 2 8 0 10 5 15 3 4 8 2 12 23 1 19 9 23 4 18 6 17 3 23 1 1 8 12 2 7 4 28 11 1 3 17 4 27 7 1 3 13 0 15 4 16 5 10 8 0 8 20 12 15 3 5...
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
14 24 16 2 1 11 11 18 14 13 0 5 14 23 1 0 3 16 6 4 3 20 6 23 3 7 0 11 12 23 11 12 12 8 2 1 1 6 12 20 5 10 15 23 13 21 4 6 8 20 11 10 1 15 6 15 4 21 7
output:
6
result:
ok single line: '6'
Subtask #3:
score: 1
Accepted
Test #8:
score: 1
Accepted
time: 1182ms
memory: 58908kb
input:
300000 500 500 421 468 185 479 155 271 218 315 136 46 248 486 179 497 389 220 462 179 144 430 112 354 231 158 127 236 229 416 219 177 144 104 223 380 23 224 67 223 165 352 494 10 270 479 418 438 239 419 315 68 346 356 140 343 11 496 327 463 435 468 213 9 113 153 168 136 246 46 101 318 58 268 430 437...
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 1161ms
memory: 58904kb
input:
300000 500 500 432 157 21 71 265 323 172 325 475 155 436 150 250 411 221 336 462 147 5 71 223 379 215 373 482 142 2 162 273 353 252 402 1 115 455 73 226 428 269 440 420 97 499 146 195 407 261 374 22 99 5 174 174 352 237 398 5 141 485 102 286 422 214 323 474 105 493 98 188 358 267 421 445 92 459 80 2...
output:
63504
result:
ok single line: '63504'
Subtask #4:
score: 1
Accepted
Test #10:
score: 1
Accepted
time: 4ms
memory: 4068kb
input:
3000 12000 12000 2012 1083 11297 11473 9823 8832 1481 3061 6929 669 8827 1919 1896 6879 8401 11178 10125 4071 3253 4791 9490 7232 1197 10638 4670 10944 10623 11596 6817 5359 11057 7906 7377 4044 3127 3553 9629 10582 562 2018 9634 10364 10869 3773 2489 7666 11655 9438 11466 3996 9900 1884 11366 8267 ...
output:
357
result:
ok single line: '357'
Test #11:
score: 0
Accepted
time: 4ms
memory: 4176kb
input:
3000 12000 12000 8511 907 10524 352 2331 9243 600 5788 10241 2571 7513 3417 3904 7504 2291 9316 7839 2268 10129 2698 4499 8989 5057 7341 8475 3832 6360 2060 3446 7749 3444 9634 6503 1518 10152 582 4028 6248 3445 5619 10781 938 7078 3356 5035 7356 3797 7915 8581 11832 6604 2220 4323 8871 4421 7452 88...
output:
4026042
result:
ok single line: '4026042'
Subtask #5:
score: 1
Accepted
Test #12:
score: 1
Accepted
time: 14ms
memory: 5236kb
input:
10000 200000 200000 184716 53950 153133 10890 77308 144936 154744 14857 43426 48885 119218 71388 174535 171297 55067 152012 144030 115963 165047 41616 123368 166389 108800 186360 19713 159152 174981 91372 68026 82048 104006 52229 155031 12975 42666 39428 102542 49441 130372 3869 198431 127930 185935...
output:
9690
result:
ok single line: '9690'
Test #13:
score: 0
Accepted
time: 14ms
memory: 5256kb
input:
10000 200000 200000 109292 19245 80948 22044 56513 104751 189838 78889 79759 179487 156175 148184 186855 113979 195528 93309 99856 155495 146452 177705 6825 111837 180923 113539 137606 196397 76332 167833 45340 112623 20543 41529 133753 182552 141010 139351 197 69395 49187 74819 128165 184529 166094...
output:
1054560
result:
ok single line: '1054560'
Subtask #6:
score: 1
Accepted
Test #14:
score: 1
Accepted
time: 48ms
memory: 8584kb
input:
30000 3000000 3000000 578339 969335 978969 2400194 2656440 1675791 1039641 1078519 438133 139918 567145 1894438 827318 1482179 827223 665090 1871822 251855 1954343 1487318 446753 984011 1996685 1331359 688292 1575935 2475339 2902692 1411124 1006160 2488580 2367281 764221 2535413 1057299 636297 14081...
output:
396352
result:
ok single line: '396352'
Test #15:
score: 0
Accepted
time: 19ms
memory: 6668kb
input:
30000 60000 60000 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50...
output:
900000000
result:
ok single line: '900000000'
Subtask #7:
score: 1
Accepted
Test #16:
score: 1
Accepted
time: 245ms
memory: 21108kb
input:
100000 50000000 50000000 33057748 46284720 44088452 38894148 31248074 27419959 16151381 9037432 12134455 32187161 24068574 34758505 47003545 24193061 39657781 10171014 21665921 22295899 25209914 33914493 47866773 20100126 48768219 43156473 33291335 25543727 41707951 43914012 2288686 34953376 3815631...
output:
9733500
result:
ok single line: '9733500'
Test #17:
score: 0
Accepted
time: 258ms
memory: 21316kb
input:
100000 50000000 50000000 39328514 18900700 43208294 6571455 468453 38684991 14947054 617723 37518073 22719790 41570369 26156182 45108163 30477923 10146104 45364687 23866353 18357213 22023302 20241500 9215802 49284737 688139 49410788 33999448 20422267 25702119 11880660 2013127 38531627 48799942 44771...
output:
442143766
result:
ok single line: '442143766'
Test #18:
score: 0
Accepted
time: 251ms
memory: 22088kb
input:
100000 700222 700222 211915 211915 562026 562026 232488 232488 582599 582599 313231 313231 663342 663342 342850 342850 692961 692961 209247 209247 559358 559358 158008 158008 508119 508119 250142 250142 600253 600253 73490 73490 423601 423601 212688 212688 562799 562799 246548 246548 596659 596659 3...
output:
16
result:
ok single line: '16'
Test #19:
score: 0
Accepted
time: 252ms
memory: 22020kb
input:
100000 700410 700410 252194 252194 602399 602399 231274 231274 581479 581479 242858 242858 593063 593063 60273 60273 410478 410478 350149 350149 700354 700354 174083 174083 524288 524288 77474 77474 427679 427679 139778 139778 489983 489983 293652 293652 643857 643857 13377 13377 363582 363582 32520...
output:
16
result:
ok single line: '16'
Test #20:
score: 0
Accepted
time: 246ms
memory: 21996kb
input:
100000 700422 700422 340081 340081 690292 690292 62795 62795 413006 413006 164988 164988 515199 515199 233795 233795 584006 584006 345994 345994 696205 696205 239106 239106 589317 589317 113356 113356 463567 463567 316088 316088 666299 666299 4174 4174 354385 354385 254538 254538 604749 604749 14069...
output:
16
result:
ok single line: '16'
Test #21:
score: 0
Accepted
time: 273ms
memory: 21112kb
input:
100000 699880 699880 256216 256216 606156 606156 92589 92589 442529 442529 99846 99846 449786 449786 288086 288086 638026 638026 124359 124359 474299 474299 306161 306161 656101 656101 100588 100588 450528 450528 193799 193799 543739 543739 148354 148354 498294 498294 294355 294355 644295 644295 111...
output:
16
result:
ok single line: '16'
Test #22:
score: 0
Accepted
time: 242ms
memory: 22164kb
input:
100000 700704 700704 245674 245674 596026 596026 316013 316013 666365 666365 74628 74628 424980 424980 211412 211412 561764 561764 142179 142179 492531 492531 348592 348592 698944 698944 242255 242255 592607 592607 206938 206938 557290 557290 14591 14591 364943 364943 217966 217966 568318 568318 244...
output:
16
result:
ok single line: '16'
Subtask #8:
score: 1
Accepted
Test #23:
score: 1
Accepted
time: 1239ms
memory: 57376kb
input:
300000 300000000 300000000 114880955 26083754 44714288 207221195 93880242 200935232 253440644 15036486 158739748 182546945 103220647 177557036 230350762 110903943 162824509 54007119 45763630 7294471 277109476 28207514 227696651 295201144 135493078 228388525 198589270 257929630 148592406 107558314 67...
output:
44856086
result:
ok single line: '44856086'
Test #24:
score: 0
Accepted
time: 1157ms
memory: 59052kb
input:
300000 300000000 300000000 222901845 243726331 182312946 257133966 34300874 181266610 2560928 142972554 188672590 247385874 186979085 30211679 54912718 141998643 29802038 97993410 228429778 236274410 168049057 31010862 99664903 188434351 125885885 107057611 278158257 53016397 205573724 262991163 567...
output:
472965225
result:
ok single line: '472965225'
Test #25:
score: 0
Accepted
time: 1177ms
memory: 58716kb
input:
300000 2099708 2099708 1037810 1037810 2087664 2087664 59456 59456 1109310 1109310 1445 1445 1051299 1051299 655775 655775 1705629 1705629 41086 41086 1090940 1090940 704551 704551 1754405 1754405 838640 838640 1888494 1888494 412512 412512 1462366 1462366 710129 710129 1759983 1759983 895323 895323...
output:
16
result:
ok single line: '16'
Test #26:
score: 0
Accepted
time: 1167ms
memory: 57492kb
input:
300000 2099898 2099898 37385 37385 1087334 1087334 342108 342108 1392057 1392057 313939 313939 1363888 1363888 545866 545866 1595815 1595815 868571 868571 1918520 1918520 528037 528037 1577986 1577986 523656 523656 1573605 1573605 19528 19528 1069477 1069477 729877 729877 1779826 1779826 595661 5956...
output:
16
result:
ok single line: '16'
Test #27:
score: 0
Accepted
time: 1115ms
memory: 59352kb
input:
300000 2099606 2099606 871639 871639 1921442 1921442 356833 356833 1406636 1406636 725780 725780 1775583 1775583 323014 323014 1372817 1372817 699936 699936 1749739 1749739 667832 667832 1717635 1717635 946403 946403 1996206 1996206 963252 963252 2013055 2013055 268672 268672 1318475 1318475 379444 ...
output:
16
result:
ok single line: '16'
Test #28:
score: 0
Accepted
time: 1179ms
memory: 58556kb
input:
300000 2099892 2099892 911537 911537 1961483 1961483 505267 505267 1555213 1555213 247734 247734 1297680 1297680 1006124 1006124 2056070 2056070 1035251 1035251 2085197 2085197 504563 504563 1554509 1554509 1036871 1036871 2086817 2086817 1024782 1024782 2074728 2074728 533885 533885 1583831 1583831...
output:
16
result:
ok single line: '16'
Test #29:
score: 0
Accepted
time: 1211ms
memory: 57632kb
input:
300000 2099394 2099394 170591 170591 1220288 1220288 549023 549023 1598720 1598720 248864 248864 1298561 1298561 970279 970279 2019976 2019976 162063 162063 1211760 1211760 568347 568347 1618044 1618044 938357 938357 1988054 1988054 1009550 1009550 2059247 2059247 9827 9827 1059524 1059524 632465 63...
output:
16
result:
ok single line: '16'
Subtask #9:
score: 1
Accepted
Test #30:
score: 1
Accepted
time: 2284ms
memory: 93580kb
input:
500000 1000000000 1000000000 65401546 858399139 595340124 524451757 773507921 584323128 206753741 655856890 305345041 317093270 615110928 229644432 283785669 152319638 129660495 400359577 65775071 592358579 531879682 102186956 757526529 131948529 372762102 945033771 782920691 492897422 438958300 115...
output:
227777729
result:
ok single line: '227777729'
Test #31:
score: 0
Accepted
time: 2326ms
memory: 93684kb
input:
500000 3499550 3499550 1612936 1612936 3362711 3362711 828322 828322 2578097 2578097 245866 245866 1995641 1995641 312634 312634 2062409 2062409 1026358 1026358 2776133 2776133 1137978 1137978 2887753 2887753 1347413 1347413 3097188 3097188 959934 959934 2709709 2709709 1189248 1189248 2939023 29390...
output:
16
result:
ok single line: '16'
Test #32:
score: 0
Accepted
time: 2189ms
memory: 92952kb
input:
500000 3500990 3500990 1390523 1390523 3141018 3141018 694089 694089 2444584 2444584 300084 300084 2050579 2050579 1440364 1440364 3190859 3190859 1722321 1722321 3472816 3472816 1211422 1211422 2961917 2961917 713781 713781 2464276 2464276 1135430 1135430 2885925 2885925 350103 350103 2100598 21005...
output:
16
result:
ok single line: '16'
Test #33:
score: 0
Accepted
time: 2192ms
memory: 93636kb
input:
500000 3500108 3500108 1341243 1341243 3091297 3091297 539977 539977 2290031 2290031 1119225 1119225 2869279 2869279 1098840 1098840 2848894 2848894 349463 349463 2099517 2099517 1335362 1335362 3085416 3085416 883404 883404 2633458 2633458 671601 671601 2421655 2421655 7422 7422 1757476 1757476 140...
output:
16
result:
ok single line: '16'
Test #34:
score: 0
Accepted
time: 2221ms
memory: 93740kb
input:
500000 3500188 3500188 1493560 1493560 3243654 3243654 180763 180763 1930857 1930857 275987 275987 2026081 2026081 444664 444664 2194758 2194758 861030 861030 2611124 2611124 1367263 1367263 3117357 3117357 1503410 1503410 3253504 3253504 1713034 1713034 3463128 3463128 1268369 1268369 3018463 30184...
output:
16
result:
ok single line: '16'
Test #35:
score: 0
Accepted
time: 2210ms
memory: 93580kb
input:
500000 3500724 3500724 722676 722676 2473038 2473038 1719845 1719845 3470207 3470207 86070 86070 1836432 1836432 251602 251602 2001964 2001964 796480 796480 2546842 2546842 1747237 1747237 3497599 3497599 37920 37920 1788282 1788282 644781 644781 2395143 2395143 1321832 1321832 3072194 3072194 37309...
output:
16
result:
ok single line: '16'
Subtask #10:
score: 1
Accepted
Test #36:
score: 1
Accepted
time: 0ms
memory: 3512kb
input:
5 1000000000 1000000000 331561509 590714524 801452152 291424474 1554859 532223439 719464478 68217028 951950334 478233809 385958855 936780365 897045194 415608756 972821795 200771613 438237327 677422687 34199073 437548595
output:
77123230925383608
result:
ok single line: '77123230925383608'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1 1000000000 1000000000 620145951 108484233 245602111 590222690
output:
324149874560454880
result:
ok single line: '324149874560454880'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
8 849 999999998 463 339800655 406 324386208 431 413559628 660 583151861 363 963644947 86 650301587 538 365754239 781 866245869 642 765046910 783 982604200 69 214902510 150 55080043 682 865830209 16 717510889 352 614276114 50 736483276
output:
41998450846
result:
ok single line: '41998450846'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
7 999999999 1342 918890070 414 866097970 252 470663409 317 155011454 1004 356490468 595 517220481 919 68362007 637 713835321 955 242663271 461 843048076 735 75616045 221 881176433 158 874217185 103 65927771 821
output:
86707144440
result:
ok single line: '86707144440'
Extra Test:
score: 0
Extra Test Passed