oj.uz

답안 #729883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
729883 2023-04-24T18:47:16 Z Denkata 사다리꼴 (balkan11_trapezoid) C++14
97 / 100
 131 ms 20800 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=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;
}

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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 340 KB Partially correct
2 Correct 0 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 2 ms 788 KB Output is correct
6 Correct 3 ms 1104 KB Output is correct
7 Correct 5 ms 1360 KB Output is correct
8 Correct 6 ms 1484 KB Output is correct
9 Correct 11 ms 2376 KB Output is correct
10 Correct 22 ms 4664 KB Output is correct
11 Correct 34 ms 5496 KB Output is correct
12 Correct 61 ms 10116 KB Output is correct
13 Correct 71 ms 12972 KB Output is correct
14 Correct 93 ms 15252 KB Output is correct
15 Correct 96 ms 15644 KB Output is correct
16 Correct 109 ms 17296 KB Output is correct
17 Correct 117 ms 18460 KB Output is correct
18 Correct 123 ms 19204 KB Output is correct
19 Correct 114 ms 19168 KB Output is correct
20 Correct 131 ms 20800 KB Output is correct