Submission #924051

#TimeUsernameProblemLanguageResultExecution timeMemory
924051Warinchaitrapezoid (balkan11_trapezoid)C++14
5 / 100
146 ms39712 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int md=30013; int sec=0; struct trap{ int a,b,c,d; int id; trap(int w=0,int x=0,int y=0,int z=0,int i=0){ a=w,b=x,c=y,d=z; id=i; } bool operator<(const trap &x){ if(sec==0)return a<x.a; return c<x.c; } }; struct segtree{ struct node{ int val,cnt; node(int v=0,int cn=0){ val=v,cnt=cn; } friend node operator+(node a,node b){ node c; c.val=max(a.val,b.val); c.cnt=(a.val==b.val?a.cnt+b.cnt:(a.val>b.val?a.cnt:b.cnt))%md; return c; } }; node info[1600005]; void upd(int st,int en,int i,int pos,int val,int cnt){ if(st>pos||en<pos)return; if(st==en)return void(info[i]=node(val,cnt)); int m=(st+en)/2; upd(st,m,i*2,pos,val,cnt); upd(m+1,en,i*2+1,pos,val,cnt); info[i]=info[i*2]+info[i*2+1]; } node fans(int st,int en,int i,int l,int r){ if(st>r||en<l)return node(); if(st>=l&&en<=r)return info[i]; int m=(st+en)/2; return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r); } }tr; queue<pair<pair<int,int>,pair<int,int> >>q; vector<trap>vb; vector<trap>v; vector<int>ord; int num[100005][2]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; for(int i=0;i<n;i++){ int a,b,c,d; cin>>a>>b>>c>>d; v.push_back(trap(a,b,c,d,i)); vb.push_back(trap(a,b,c,d,i)); ord.push_back(a); ord.push_back(b); ord.push_back(c); ord.push_back(d); } sort(ord.begin(),ord.end()); sort(v.begin(),v.end()); sec=1; sort(vb.begin(),vb.end()); int cur=0; for(int i=0;i<v.size();i++){ while(cur<n&&vb[cur].b<v[i].a){ int pos=lower_bound(ord.begin(),ord.end(),vb[cur].d)-ord.begin()+1; tr.upd(1,4*n,1,pos,num[vb[cur].id][0],num[vb[cur].id][1]); cur++; } int pos=lower_bound(ord.begin(),ord.end(),v[i].c-1)-ord.begin()+1; auto temp=tr.fans(1,4*n,1,1,pos); num[v[i].id][0]=temp.val+1; num[v[i].id][1]=temp.val==0?1:temp.cnt; //cerr<<v[i].id<<" "<<num[v[i].id][0]<<" "<<num[v[i].id][1]<<"\n"; } while(cur<n){ int pos=lower_bound(ord.begin(),ord.end(),vb[cur].d)-ord.begin()+1; tr.upd(1,4*n,1,pos,num[vb[cur].id][0],num[vb[cur].id][1]); cur++; } cout<<tr.info[1].val<<" "<<tr.info[1].cnt; }

Compilation message (stderr)

trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<trap>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...