제출 #729885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729885		Denkata	사다리꼴 (balkan11_trapezoid)	C++14	97 / 100	126 ms	20708 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
const long long maxn = 1e5+3;
const long long maxq = 4e5+3;
const long long mod = 30013;
long long i,j,p,q,n,m,k;
pair <long long,long long> dp[maxn];
pair <long long,long long> a[maxn];

struct Trapeze
{
    long long a[5];///a b c d
}tr[maxn];
struct Coordinate
{
    long long val;
    long long type;
    long long ind;
};
vector <Coordinate> coordinates;
bool ul[maxq],ur[maxq];
pair <long long,long long> fen[maxq];
void upd(long long p,long long d,long long br)
{
    while(p<=maxq)
    {
        if(d>fen[p].first)
            fen[p] = {d,br};
        else if(d==fen[p].first)
            fen[p].second+=br,fen[p].second%=mod;
        p = (p|(p+1));
    }
}
pair <long long,long long> rsq(long long p)
{
    pair <long long,long long> ans={0,0};
    while(p>0)
    {
        if(ans.first<fen[p].first)
            ans = fen[p];
        else if(ans.first==fen[p].first)
            ans.second+=fen[p].second,ans.second%=mod;
        p = ((p&(p+1))-1);
    }
    return ans;
}
bool fff(Coordinate a,Coordinate b)
{
    return a.val<b.val;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>tr[i].a[1]>>tr[i].a[2]>>tr[i].a[3]>>tr[i].a[4];
        coordinates.push_back({tr[i].a[1],1,i});
        coordinates.push_back({tr[i].a[2],2,i});
        coordinates.push_back({tr[i].a[3],3,i});
        coordinates.push_back({tr[i].a[4],4,i});
    }
    sort(coordinates.begin(),coordinates.end(),fff);
    for(i=0;i<coordinates.size();i++)
    {
        auto t = coordinates[i];
        tr[t.ind].a[t.type] = i+1;
    }
    coordinates.push_back({4*n+2,1,n+1});
    tr[n+1].a[3]=4*n+2;
    upd(0,0,1);
    for(i=1;i<=4*n+1;i++)
    {
        auto t = coordinates[i];
        if(t.type==1)
        {
            dp[t.ind] = rsq(tr[t.ind].a[3]);
            dp[t.ind].first++;
        }
        else if(t.type==2)
        {
            upd(tr[t.ind].a[4],dp[t.ind].first,dp[t.ind].second);
        }
    }
    pair <long long,long long> ans = rsq(4*n+2);
    cout<<ans.first<<" "<<ans.second<<endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Coordinate>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(i=0;i<coordinates.size();i++)
      |             ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 97 / 100