oj.uz

답안 #729890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
729890 2023-04-24T18:52:06 Z Denkata 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 119 ms 20748 KB 
#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=0;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+3);
    cout<<ans.first<<" "<<ans.second<<endl;
    return 0;
}

Compilation message

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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 788 KB Output is correct
6 Correct 4 ms 1104 KB Output is correct
7 Correct 5 ms 1360 KB Output is correct
8 Correct 5 ms 1484 KB Output is correct
9 Correct 11 ms 2376 KB Output is correct
10 Correct 21 ms 4668 KB Output is correct
11 Correct 26 ms 5600 KB Output is correct
12 Correct 57 ms 10136 KB Output is correct
13 Correct 74 ms 13056 KB Output is correct
14 Correct 86 ms 15232 KB Output is correct
15 Correct 96 ms 15732 KB Output is correct
16 Correct 101 ms 17240 KB Output is correct
17 Correct 108 ms 18432 KB Output is correct
18 Correct 104 ms 19224 KB Output is correct
19 Correct 112 ms 19252 KB Output is correct
20 Correct 119 ms 20748 KB Output is correct