Submission #377670

#	Time	Username	Problem	Language	Result	Execution time	Memory
377670		ntabc05101	trapezoid (balkan11_trapezoid)	C++14	100 / 100	292 ms	39108 KiB

trapezoid

#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

#define taskname ""

#define f first
#define s second

const int max_n=500000;
const int inf=1e9+9;
const int mod=30013;

std::vector<int> pList[max_n+1];
std::pair<int, int> bits[max_n+1];

void update(int x, std::pair<int, int> delta) {
        for (; x<=max_n; x+=x&-x) {
                if (bits[x].f<delta.f) {
                        bits[x]=delta;
                }
                else if (bits[x].f==delta.f) {
                        bits[x].s+=delta.s;
                        if (bits[x].s>=mod) {
                                bits[x].s-=mod;
                        }
                }
        }
}

std::pair<int, int> get(int x) {
        std::pair<int, int> ret={0, 0};
        for (; x>0; x&=x-1) {
                if (ret.f<bits[x].f) {
                        ret=bits[x];
                }
                else if (ret.f==bits[x].f) {
                        ret.s+=bits[x].s;
                        if (ret.s>=mod) {
                                ret.s-=mod;
                        }
                }
        }
        
        return ret;
}

int main() {
        if (fopen(taskname".inp", "r")) {
                freopen(taskname".inp", "r", stdin);
                freopen(taskname".out", "w", stdout);
        }
        else if (fopen(taskname".in", "r")) {
                freopen(taskname".in", "r", stdin);
                freopen(taskname".out", "w", stdout);
        }

        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n; std::cin>>n;
        int a[n][4];
        std::vector<int> points;
        points.push_back(inf);
        for (int i=0; i<n; ++i) {
                for (int j=0; j<4; ++j) {
                        std::cin>>a[i][j];
                        points.push_back(a[i][j]);
                }
        }

        std::sort(begin(points), end(points));
        points.resize(std::distance(begin(points), std::unique(begin(points), end(points))));
        std::unordered_map<int, int> compress;

        #define cpoint(x) (compress.count(x)>0 ? compress[x]: compress[x]=std::lower_bound(begin(points), end(points), x)-begin(points)+1)

        for (int i=0; i<n; ++i) {
                for (int j=0; j<4; ++j) {
                        a[i][j]=cpoint(a[i][j]);
                }

                pList[a[i][0]].push_back(i);
                pList[a[i][1]].push_back(i+n);
        }

        /*for (int i=0; i<n; ++i) {
                for (int j=0; j<4; ++j) std::cout<<a[i][j]<<" ";
                std::cout<<"\n";
        }*/

        update(1, {0, 1});
        std::pair<int, int> result[n];
        for (int i=1; i<=4*n; ++i) {
                for (auto& p: pList[i]) {
                        if (p<n) {
                                result[p]=get(a[p][2]);
                                ++result[p].f;
                        }
                        else {
                                update(a[p-n][3], result[p-n]);
                        }
                }
        }
        
        auto ret=get(4*n+1);
        std::cout<<ret.f<<" "<<ret.s<<"\n";

        return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:51:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   51 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:52:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   52 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:55:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |                 freopen(taskname".in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:56:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   56 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100