Submission #729885

# Submission time Handle Problem Language Result Execution time Memory
729885 2023-04-24T18:48:41 Z Denkata trapezoid (balkan11_trapezoid) C++14
97 / 100
126 ms 20708 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++)
      |             ~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 340 KB Partially correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 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 6 ms 1264 KB Output is correct
8 Correct 7 ms 1496 KB Output is correct
9 Correct 12 ms 2376 KB Output is correct
10 Correct 24 ms 4692 KB Output is correct
11 Correct 27 ms 5472 KB Output is correct
12 Correct 80 ms 10180 KB Output is correct
13 Correct 71 ms 12984 KB Output is correct
14 Correct 88 ms 15236 KB Output is correct
15 Correct 95 ms 15688 KB Output is correct
16 Correct 115 ms 17180 KB Output is correct
17 Correct 108 ms 18388 KB Output is correct
18 Correct 111 ms 19252 KB Output is correct
19 Correct 126 ms 19228 KB Output is correct
20 Correct 118 ms 20708 KB Output is correct