QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#415665 | #4236. Triangular Logs | littlecat# | ML | 78ms | 21584kb | C++23 | 2.3kb | 2024-05-21 08:31:13 | 2024-05-21 08:31:14 |
Judging History
answer
#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
#include <vector>
#define pb push_back
template<class C> using vc=vector<C>;
#include <algorithm>
#define For(i,a,b) for(int i=(a);i<(b);i++)
#define smax(a,b) a=max(a,b)
#define f first
#define s second
typedef pair<int,int> pi;
const int mx=100000, T=50, sz=1000000001;
//if no triangle, heights must be fibonacci
//phi^10 = L_10 = (2) 1 3 4 7 11 18 29 47 76 (123)
//phi^50 > 2*10^10 -> 50 suffices
vc<int> V; int qx,qy,qv, qxl,qxr,qyl,qyr;
namespace node
{
const int N=50000000;
int alloc=0;
int l[N],r[N]; vc<int> v[N];
void ins(int i, int L, int R)
{
if(qy<L||qy>=R) return;
if(v[i].size()<T) v[i].pb(qv);
if(R==L+1) return;
if(!l[i]) l[i]=alloc++, r[i]=alloc++;
ins(l[i],L,(L+R)>>1), ins(r[i],(L+R)>>1,R);
}
void qry(int i, int L, int R)
{
if(V.size()>=T||qyl>=R||qyr<=L||v[i].empty()) return;
if(qyl<=L&&qyr>=R)
{
for(int t:v[i]) if(V.size()<T) V.pb(t);
return;
}
if(!l[i]) return;
qry(l[i],L,(L+R)>>1), qry(r[i],(L+R)>>1,R);
}
}
namespace Node
{
const int N=1000000;
int alloc=1; //node 0 is root, already used
int l[N],r[N]; int v[N];
void ins(int i, int L, int R)
{
if(qx<L||qx>=R) return;
node::ins(v[i],0,sz);
if(R==L+1) return;
if(!l[i]) l[i]=alloc++, r[i]=alloc++,
v[l[i]]=node::alloc++, v[r[i]]=node::alloc++;
ins(l[i],L,(L+R)>>1), ins(r[i],(L+R)>>1,R);
}
void qry(int i, int L, int R)
{
if(V.size()>=T||qxl>=R||qxr<=L) return;
if(qxl<=L&&qxr>=R)
{
node::qry(v[i],0,sz);
return;
}
if(!l[i]) return;
qry(l[i],L,(L+R)>>1), qry(r[i],(L+R)>>1,R);
}
}
int main()
{
cin.sync_with_stdio(0), cin.tie(0), cout.sync_with_stdio(0), cout.tie(0);
int n,q; cin>>n>>q;
For(i,0,n) cin>>qx>>qy>>qv, Node::ins(0,0,sz);
For(i,0,q)
{
cin>>qxl>>qyl>>qxr>>qyr,qxr++,qyr++, V.clear(), Node::qry(0,0,sz);
sort(V.begin(),V.end());
int ans=0;
for(int i=0; i+2<V.size(); i++) if(V[i]+V[i+1]>V[i+2]) ans=1;
cout<<ans<<'\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 63ms
memory: 3772kb
input:
9 5 1 3 3 2 3 1 3 3 4 1 2 1 2 2 5 3 2 9 1 1 2 2 1 6 3 1 5 1 1 1 2 1 1 2 2 1 1 1 3 1 2 3 2 1 1 3 3
output:
0 1 0 0 1
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 74ms
memory: 18888kb
input:
481 1 8 6788 8975 24 6552 2668 26 7948 4730 40 531 9805 110 1914 1916 164 7073 3371 165 6293 7756 170 9946 2003 179 9654 1700 215 6447 2229 221 3149 3030 242 1999 6843 242 5764 3163 249 3716 8634 250 6801 9317 260 2741 4273 282 5436 4836 284 3951 6483 288 4812 76 375 9004 5492 380 5627 5929 391 6385...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 78ms
memory: 21584kb
input:
378 1 62730 50925 80731 92666 77280 61521 29236 67032 7889 35986 96802 8763 13313 49918 83582 51842 66775 47834 2286 12925 41106 39790 6698 15243 65145 56379 68496 35570 809 525 39834 16723 48002 77230 16273 16032 52615 7621 77300 92267 82517 39917 13170 89084 77751 45638 23868 49631 7758 71381 5191...
output:
1
result:
ok single line: '1'
Test #4:
score: -100
Memory Limit Exceeded
input:
100000 100000 299999993 206450345 26023928 334281171 300000008 18107965 318653732 299999990 82338399 299999997 393028366 37212808 299999992 208114125 82126189 300000002 303613195 34463905 270033576 299999993 49200970 300000003 249755524 5829381 300000003 367329175 12867359 300000009 337452692 131045...