답안 #924048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924048 2024-02-08T10:26:51 Z Warinchai 사다리꼴 (balkan11_trapezoid) C++14
5 / 100
126 ms 22244 KB
#include<bits/stdc++.h>
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];
int 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)-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

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<trap>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13400 KB Output is correct
2 Incorrect 3 ms 13404 KB Output isn't correct
3 Incorrect 3 ms 13492 KB Output isn't correct
4 Incorrect 4 ms 13716 KB Output isn't correct
5 Incorrect 5 ms 13660 KB Output isn't correct
6 Incorrect 6 ms 13916 KB Output isn't correct
7 Incorrect 9 ms 13916 KB Output isn't correct
8 Incorrect 8 ms 14172 KB Output isn't correct
9 Incorrect 13 ms 14560 KB Output isn't correct
10 Incorrect 23 ms 15568 KB Output isn't correct
11 Incorrect 30 ms 16040 KB Output isn't correct
12 Incorrect 60 ms 18060 KB Output isn't correct
13 Incorrect 76 ms 18736 KB Output isn't correct
14 Incorrect 91 ms 20784 KB Output isn't correct
15 Incorrect 96 ms 21560 KB Output isn't correct
16 Incorrect 104 ms 21564 KB Output isn't correct
17 Incorrect 107 ms 21564 KB Output isn't correct
18 Incorrect 98 ms 21728 KB Output isn't correct
19 Incorrect 114 ms 22244 KB Output isn't correct
20 Incorrect 126 ms 22056 KB Output isn't correct