QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#854944 | #9240. Mosaic | 275307894a# | 12 | 406ms | 339492kb | C++20 | 2.6kb | 2025-01-12 11:12:06 | 2025-01-12 11:12:10 |
Judging History
answer
#include "mosaic.h"
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e5+5,M=(1<<28)+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int c1[205][N],c2[N][205],a[N],b[N];
int n,q;
ll sb1[N],sb2[N],sa1[N],sa2[N];
ll calc(int x,int y){
if(x==-1||y==-1) return 0;
if(x<=50) return c1[x][y];
if(y<=50) return c2[x][y];
ll tot=c1[49][y]+c2[x][49]-c1[49][49];
int pb=x-y+50;
if(pb<=50){
tot+=(x+1)*sb1[x]-sb2[x];
}else{
tot+=(y-50+1)*sb1[pb]+(x+1)*(sb1[x]-sb1[pb])-(sb2[x]-sb2[pb]);
}
for(int i=50;i<=x;i++) tot+=b[i]*min(x-i+1,y-50+1);
for(int i=50+1;i<=y;i++) tot+=a[i]*min(x-50+1,y-i+1);
return tot;
}
vector<long long> mosaic(vector<int> X,vector<int> Y,vector<int> T,vector<int> B,vector<int> L,vector<int> R) {
n=X.size();q=T.size();
for(int i=0;i<n;i++) c1[0][i]=X[i],c2[i][0]=Y[i];
for(int i=0;i<=200&&i<n;i++) c1[i][0]=Y[i],c2[0][i]=X[i];
for(int i=1;i<=200;i++) for(int j=1;j<=n;j++) c1[i][j]=(!c1[i-1][j]&&!c1[i][j-1]);
for(int i=1;i<=n;i++) for(int j=1;j<=200;j++) c2[i][j]=(!c2[i-1][j]&&!c2[i][j-1]);
for(int i=50;i<=n;i++) a[i]=c1[50][i],b[i]=c2[i][50];
for(int i=50;i<=n;i++) sb1[i]=sb1[i-1]+b[i],sb2[i]=sb2[i-1]+b[i]*i;
for(int i=51;i<=n;i++) sa1[i]=sa1[i-1]+a[i],sa2[i]=sa2[i-1]+a[i]*i;
for(int i=0;i<=200;i++) for(int j=0;j<=n;j++) if(i) c1[i][j]+=c1[i-1][j];
for(int i=0;i<=200;i++) for(int j=0;j<=n;j++) if(j) c1[i][j]+=c1[i][j-1];
for(int i=0;i<=n;i++) for(int j=0;j<=200;j++) if(i) c2[i][j]+=c2[i-1][j];
for(int i=0;i<=n;i++) for(int j=0;j<=200;j++) if(j) c2[i][j]+=c2[i][j-1];
vector<ll> ans(q);
for(int i=0;i<q;i++){
// for(int j=T[i];j<=B[i];j++) for(int h=L[i];h<=R[i];h++) ans[i]+=c2[j][h];
ans[i]=calc(B[i],R[i])-calc(T[i]-1,R[i])-calc(B[i],L[i]-1)+calc(T[i]-1,L[i]-1);
}
return ans;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 65760kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 1 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 0 0 0 0 0 0 0 0 0 0
result:
ok
Test #2:
score: 5
Accepted
time: 0ms
memory: 61704kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 1 1 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 1 1 1 1 1 1 1 1 1 1
result:
ok
Test #3:
score: 5
Accepted
time: 0ms
memory: 47748kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 1 0 1 0 10 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 1 1 1 2 2 0 2 1 1 1
result:
ok
Test #4:
score: 5
Accepted
time: 0ms
memory: 61664kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 1 0 1 0 10 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 1 1 0 0
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 1 2 1 1 2 1 1 1 1 0
result:
ok
Test #5:
score: 5
Accepted
time: 0ms
memory: 61744kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 0 1 0 0 10 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 0 1 0 0 0 0 1 1 1 1
result:
ok
Test #6:
score: 5
Accepted
time: 0ms
memory: 47432kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 1 1 1 0 10 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 2 2 0 2 1 1 0 1 1 1
result:
ok
Test #7:
score: 5
Accepted
time: 3ms
memory: 61648kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 0 0 0 1 10 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 0 1 1 1 0 0 0 1 1 1
result:
ok
Test #8:
score: 5
Accepted
time: 3ms
memory: 69844kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 1 0 1 1 10 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 2 1 1 0 1 0 2 0 1 2
result:
ok
Test #9:
score: 5
Accepted
time: 3ms
memory: 75980kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 0 1 0 1 10 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 2 2 0 2 1 2 1 0 1 2
result:
ok
Test #10:
score: 5
Accepted
time: 0ms
memory: 88460kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 2 1 1 1 1 10 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 2 2 2 3 1 3 3 1 3 0
result:
ok
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 96460kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 199 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 0 1...
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 1102 5781 1178 778 13522 1704 3133 6569 697 2800 34 430 1143 7735 6039 629 58 20 392 555 5392 87 6605 49 1368 2354 80 1525 1958 6509 7067 2692 56 3308 1918 106 4436 3110 327 3483 436 1824 901 1643 1362 8551 3272 3055 490 5590 2756 5159 975 2318 1992 2509 75 13589 ...
result:
wrong answer 3rd lines differ - on the 1st token, expected: '1078', found: '1102'
Subtask #3:
score: 7
Accepted
Test #18:
score: 7
Accepted
time: 395ms
memory: 339308kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 199999 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 ...
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 1314 79312 13238 63518 27135 86532 21129 53105 14461 13920 65981 66950 13385 23885 37091 56646 69855 64947 74166 41759 50738 1366 65318 58452 24337 58380 29379 59258 39016 4990 60529 23351 60370 12835 25686 8151 17007 56172 10913 7224 30221 73673 55593 33643 44070...
result:
ok
Test #19:
score: 7
Accepted
time: 372ms
memory: 339112kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 199999 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 ...
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 97288 84412 98958 98546 95894 91536 99791 94852 96879 98784 94005 99030 95916 90829 96593 96545 90518 95251 93882 95122 94925 96009 98788 98866 95996 97263 95422 95733 96576 97730 98106 96939 94030 94576 94019 92982 96921 95715 96639 93579 97372 97983 95123 95211 ...
result:
ok
Test #20:
score: 7
Accepted
time: 392ms
memory: 339056kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 200000 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 ...
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 63186 59869 80378 71302 94439 63006 84372 99459 21243 54879 86436 65742 94261 35276 55849 93734 72881 49090 34951 93280 90257 58145 84070 58055 95069 56733 82475 51301 59357 39555 95572 87255 37523 68017 80309 52815 95469 29140 85700 46052 56013 71305 90947 7434 6...
result:
ok
Test #21:
score: 7
Accepted
time: 406ms
memory: 339492kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 200000 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 ...
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 99156 96398 98499 93058 98359 93547 93120 98997 99065 97926 99050 95046 96687 98137 97249 97530 96983 98126 89892 94397 98111 96471 95754 99320 97511 95029 96780 93937 97095 97566 97024 99338 97729 99722 97152 98216 95895 97942 98980 99845 96992 97397 99255 97894 ...
result:
ok
Test #22:
score: 7
Accepted
time: 218ms
memory: 187428kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 100000 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 ...
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 34862 31357 15637 16893 7670 123 17919 20936 7467 18723 34082 1835 18668 23866 630 26206 40304 6217 25617 18490 11507 39163 5570 16345 4695 30449 15992 13307 5315 5393 8864 29876 34139 3227 28910 11628 2250 38538 12586 299 1066 8238 40627 7418 7600 3123 18111 9012...
result:
ok
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Time Limit Exceeded
Test #31:
score: 8
Accepted
time: 41ms
memory: 97616kb
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 200000 1 7 0 4 3 4 3 4 3 6 2 5 4 5 6 7 5 7 2 8 0 6 4 7 0 5 6 7 1 3 9 9 6 9 1 7 2 9 4 6 4 4 6 7 0 1 8 8 7 7 0 3 0 4 1 7 2 2 0 9 3 9 4 6 3 9 0 9 1 8 4 6 4 5 5 7 0 6 2 3 2 3 0 6 1 9 8 8 2 4 3 4 3 6 2 9 3 9 2 7 1 3 0 3 0 8 2 4 3...
output:
Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9 OK 14 2 8 2 10 12 5 2 14 12 1 0 2 14 4 10 32 12 3 6 6 4 3 16 21 5 12 6 7 11 12 3 7 3 6 15 6 4 6 8 15 24 2 5 11 8 16 3 4 12 4 9 23 1 2 5 6 4 1 4 4 3 6 4 18 32 10 2 7 7 5 12 11 7 4 4 10 6 4 16 8 13 8 3 3 8 21 1 2 3 6 14 21 14 9 2 3 2 4 16 20 7 3 5 3 15 16 8 36 7 6 7 9 ...
result:
ok
Test #32:
score: 0
Time Limit Exceeded
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 199999 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
result:
Subtask #6:
score: 0
Time Limit Exceeded
Test #42:
score: 0
Time Limit Exceeded
input:
njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq 199999 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 1 ...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #3:
100%
Accepted
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%