QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185337 | #7182. Very Sparse Table | 275307894a | AC ✓ | 549ms | 10792kb | C++14 | 1.9kb | 2023-09-21 21:26:38 | 2023-09-21 21:26:39 |
Judging History
answer
#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
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>;using LL=__int128;
const int N=2e5+5,M=N*20+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(263082);
int n,m;
vector<tuple<int,int,int> > ans;vector<int> tot;
void con(int x,int z,int y){if(x<z&&z<y) ans.emplace_back(x,z,y);}
void solve(int l,int r){
if(r-l<=3) return;
int BB=sqrt((r-l)*0.9);
for(int i=l+BB-1;i<=r;i+=BB){
for(int j=i-1;j>i-BB;j--) con(j,j+1,i);
for(int j=i+1;j<i+BB&&j<=n;j++) con(i,j-1,j);
for(int j=i-BB;j>=l;j-=BB) con(j,j==i-BB?j+1:j+BB,i);
}
int i;
for(i=l+BB-1;i<=r;i+=BB) solve(i-BB+1,i);
solve(i-BB+1,r);
}
void qry(int x,int y,int l,int r){
if(r-l<=3){
for(int i=x;i<=y;i++) tot.emplace_back(i);
return;
}
int BB=sqrt((r-l)*0.9);
int X=x,Y=y;
while(X<=r&&(X-l)%BB!=BB-1) X++;
while(Y>=l&&(Y-l)%BB!=BB-1) Y--;
if(X>Y) return qry(x,y,Y+1,X-1);
tot={x,X,Y,y};
}
void Solve(){
int i,j;cin>>n;
solve(0,n);
cout<<ans.size()<<'\n';
for(auto i:ans){
int x,y,z;tie(x,y,z)=i;
cout<<x<<' '<<y<<' '<<z<<'\n';
} fflush(stdout);
int q;cin>>q;//cout<<"ZJAKIOI";
ans.clear();
while(q--){
int x,y;cin>>x>>y;
tot.clear();qry(x,y,0,n);
sort(tot.begin(),tot.end());tot.erase(unique(tot.begin(),tot.end()),tot.end());
for(int i:tot) cout<<i<<' ';cout<<'\n';fflush(stdout);
}
}
int main(){
// freopen("1.in","r",stdin);
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
input:
9 45 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 4 3 5 3 6 3 7 3 8 3 9 4 5 4 6 4 7 4 8 4 9 5 6 5 7 5 8 5 9 6 7 6 8 6 9 7 8 7 9 8 9
output:
10 1 2 3 3 4 5 1 3 5 5 6 7 3 5 7 1 3 7 7 8 9 5 7 9 3 5 9 1 3 9 0 1 0 1 2 0 1 3 0 1 3 4 0 1 5 0 1 5 6 0 1 7 0 1 7 8 0 1 9 1 2 1 3 1 3 4 1 5 1 5 6 1 7 1 7 8 1 9 2 3 2 3 4 2 3 5 2 3 5 6 2 3 7 2 3 7 8 2 3 9 3 4 3 5 3 5 6 3 7 3 7 8 3 9 4 5 4 5 6 4 5 7 4 5 7 8 4 5 9 5 6 ...
result:
ok edges: 10
Test #2:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
30 465 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 2 3 2 4 2 5 2 6...
output:
84 2 3 4 1 2 4 0 1 4 4 5 6 4 6 7 4 7 8 7 8 9 6 7 9 5 6 9 9 10 11 9 11 12 9 12 13 4 5 9 12 13 14 11 12 14 10 11 14 14 15 16 14 16 17 14 17 18 9 10 14 4 9 14 17 18 19 16 17 19 15 16 19 19 20 21 19 21 22 19 22 23 14 15 19 9 14 19 4 9 19 22 23 24 21 22 24 20 21 24 24 25 26 24 26 27 24 27 28 19 20 24 14 ...
result:
ok edges: 66
Test #3:
score: 0
Accepted
time: 316ms
memory: 3840kb
input:
736 200000 170 268 126 166 565 723 664 735 61 524 226 234 146 314 217 272 294 713 115 381 563 706 74 567 552 614 120 211 472 620 213 432 488 623 447 564 96 129 331 354 79 677 50 547 174 568 56 129 189 227 55 701 244 253 264 715 154 220 380 657 46 390 53 161 325 537 666 696 64 465 391 659 284 448 207...
output:
2872 22 23 24 21 22 24 20 21 24 19 20 24 18 19 24 17 18 24 16 17 24 15 16 24 14 15 24 13 14 24 12 13 24 11 12 24 10 11 24 9 10 24 8 9 24 7 8 24 6 7 24 5 6 24 4 5 24 3 4 24 2 3 24 1 2 24 0 1 24 24 25 26 24 26 27 24 27 28 24 28 29 24 29 30 24 30 31 24 31 32 24 32 33 24 33 34 24 34 35 24 35 36 24 36 37...
result:
ok edges: 2872
Test #4:
score: 0
Accepted
time: 542ms
memory: 10792kb
input:
65536 200000 51949 58727 7943 43298 6290 7369 41493 53070 24229 36675 28087 49947 11703 48217 19923 24739 2144 59777 53830 56793 13509 37211 2300 38595 27415 42879 24616 48531 58341 63327 20628 38407 48616 60290 7450 61685 37010 47595 22164 42732 19181 29850 35383 43587 39257 44397 19340 45183 34523...
output:
377646 239 240 241 238 239 241 237 238 241 236 237 241 235 236 241 234 235 241 233 234 241 232 233 241 231 232 241 230 231 241 229 230 241 228 229 241 227 228 241 226 227 241 225 226 241 224 225 241 223 224 241 222 223 241 221 222 241 220 221 241 219 220 241 218 219 241 217 218 241 216 217 241 215 2...
result:
ok edges: 372786
Test #5:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
0 0
output:
0
result:
ok edges: 0
Test #6:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1 1 0 1
output:
0 0 1
result:
ok edges: 0
Test #7:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
2 3 0 1 0 2 1 2
output:
0 0 1 0 1 2 1 2
result:
ok edges: 0
Test #8:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
3 6 0 1 0 2 0 3 1 2 1 3 2 3
output:
0 0 1 0 1 2 0 1 2 3 1 2 1 2 3 2 3
result:
ok edges: 0
Test #9:
score: 0
Accepted
time: 549ms
memory: 10244kb
input:
65535 200000 35006 46944 17075 57351 24605 50445 5938 60705 15221 40233 28599 38915 1132 35574 8555 31494 13644 35806 44940 55401 9503 59206 21011 26540 41156 62487 57510 64305 9254 25610 17301 47249 34083 49167 48018 64394 38855 62175 15464 22525 23728 60275 54028 63810 22711 53902 5984 48625 5838 ...
output:
377644 239 240 241 238 239 241 237 238 241 236 237 241 235 236 241 234 235 241 233 234 241 232 233 241 231 232 241 230 231 241 229 230 241 228 229 241 227 228 241 226 227 241 225 226 241 224 225 241 223 224 241 222 223 241 221 222 241 220 221 241 219 220 241 218 219 241 217 218 241 216 217 241 215 2...
result:
ok edges: 372784
Test #10:
score: 0
Accepted
time: 500ms
memory: 9672kb
input:
64800 200000 55124 62263 24992 39760 32262 37059 25987 42889 10413 64701 7223 43221 45810 63205 11437 29357 10814 52096 1154 36319 10730 54157 18473 26729 9152 23374 5426 12744 3502 37577 5559 37160 30503 62433 12426 47332 14933 62086 8781 21527 27180 53773 29658 46742 20592 61553 8337 27197 8024 38...
output:
374126 238 239 240 237 238 240 236 237 240 235 236 240 234 235 240 233 234 240 232 233 240 231 232 240 230 231 240 229 230 240 228 229 240 227 228 240 226 227 240 225 226 240 224 225 240 223 224 240 222 223 240 221 222 240 220 221 240 219 220 240 218 219 240 217 218 240 216 217 240 215 216 240 214 2...
result:
ok edges: 369302
Extra Test:
score: 0
Extra Test Passed