oj.uz

Submission #729882

# Submission time Handle Problem Language Result Execution time Memory
729882 2023-04-24T18:45:54 Z Denkata trapezoid (balkan11_trapezoid) C++14
97 / 100
 117 ms 13312 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+3;
const int maxq = 4e5+3;
const int mod = 30013;
int i,j,p,q,n,m,k;
pair <int,int> dp[maxn];
pair <int,int> a[maxn];

struct Trapeze
{
    int a[5];///a b c d
}tr[maxn];
struct Coordinate
{
    int val;
    int type;
    int ind;
};
vector <Coordinate> coordinates;
bool ul[maxq],ur[maxq];
pair <int,int> fen[maxq];
void upd(int p,int d,int 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 <int,int> rsq(int p)
{
    pair <int,int> 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 <int,int> 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: '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

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Partially correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 4 ms 884 KB Output is correct
7 Correct 4 ms 916 KB Output is correct
8 Correct 6 ms 1104 KB Output is correct
9 Correct 9 ms 1628 KB Output is correct
10 Correct 23 ms 3108 KB Output is correct
11 Correct 26 ms 3736 KB Output is correct
12 Correct 48 ms 6580 KB Output is correct
13 Correct 59 ms 8376 KB Output is correct
14 Correct 66 ms 9808 KB Output is correct
15 Correct 73 ms 10020 KB Output is correct
16 Correct 88 ms 11092 KB Output is correct
17 Correct 84 ms 11692 KB Output is correct
18 Correct 82 ms 12320 KB Output is correct
19 Correct 88 ms 12592 KB Output is correct
20 Correct 117 ms 13312 KB Output is correct