QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415692#4236. Triangular Logslittlecat#WA 60ms4760kbC++233.1kb2024-05-21 08:45:322024-05-21 08:45:33

Judging History

你现在查看的是最新测评结果

  • [2024-05-21 08:45:33]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:4760kb
  • [2024-05-21 08:45:32]
  • 提交

answer

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
#include <vector>
#define pb push_back
template<class C> using vc=vector<C>;
#include <map>
#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=100005, inf=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=40000000;
    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(qy<(L+R)>>1)
        {
            if(!l[i]) l[i]=alloc++;
            ins(l[i],L,(L+R)>>1);
        }
        else
        {
            if(!r[i]) r[i]=alloc++;
            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]) qry(l[i],L,(L+R)>>1);
        if(r[i]) 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(qx<(L+R)>>1)
        {
            if(!l[i]) l[i]=alloc++, v[l[i]]=node::alloc++;
            ins(l[i],L,(L+R)>>1);
        }
        else
        {
            if(!r[i]) r[i]=alloc++, v[r[i]]=node::alloc++;
            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]) qry(l[i],L,(L+R)>>1);
        if(r[i]) qry(r[i],(L+R)>>1,R);
    }
}
map<int,int> Mx, My;
int a[mx],b[mx],v[mx]; vc<int> A,B;
int main()
{
    cin.sync_with_stdio(0), cin.tie(0), cout.sync_with_stdio(0), cout.tie(0);
    int n,q; cin>>n>>q, A.resize(n),B.resize(n);
    For(i,0,n) cin>>a[i]>>b[i]>>v[i],A[i]=a[i],B[i]=b[i];
    sort(A.begin(),A.end()),sort(B.begin(),B.end()),
    A.resize(unique(A.begin(),A.end())-A.begin()),
    B.resize(unique(B.begin(),B.end())-B.begin());
    for(int t:A) Mx[t]=Mx.size(); for(int t:B) My[t]=My.size();
    Mx[inf]=Mx.size(), My[inf]=My.size();
    For(i,0,n) qx=Mx[a[i]],qv=My[b[i]],qv=v[i], Node::ins(0,0,sz);
    For(i,0,q)
    {
        cin>>qxl>>qyl>>qxr>>qyr;
        qxl=Mx.lower_bound(qxl)->s, qyl=My.lower_bound(qyl)->s;
        qxr=Mx.upper_bound(qxr)->s, qyr=My.upper_bound(qyr)->s;
        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';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 60ms
memory: 3668kb

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: -100
Wrong Answer
time: 58ms
memory: 4760kb

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:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'