oj.uz

Submission #377669

# Submission time Handle Problem Language Result Execution time Memory
377669 2021-03-14T16:50:59 Z ntabc05101 trapezoid (balkan11_trapezoid) C++14
0 / 100
 356 ms 44816 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12140 KB Output isn't correct
2 Incorrect 9 ms 12140 KB Output isn't correct
3 Incorrect 10 ms 12268 KB Output isn't correct
4 Incorrect 11 ms 12396 KB Output isn't correct
5 Incorrect 14 ms 12908 KB Output isn't correct
6 Incorrect 16 ms 13164 KB Output isn't correct
7 Incorrect 16 ms 13164 KB Output isn't correct
8 Incorrect 22 ms 13676 KB Output isn't correct
9 Incorrect 34 ms 15356 KB Output isn't correct
10 Incorrect 52 ms 17260 KB Output isn't correct
11 Incorrect 84 ms 20484 KB Output isn't correct
12 Incorrect 176 ms 28960 KB Output isn't correct
13 Incorrect 196 ms 31884 KB Output isn't correct
14 Incorrect 271 ms 37776 KB Output isn't correct
15 Incorrect 257 ms 34844 KB Output isn't correct
16 Incorrect 267 ms 36324 KB Output isn't correct
17 Incorrect 356 ms 41488 KB Output isn't correct
18 Incorrect 216 ms 35172 KB Output isn't correct
19 Incorrect 308 ms 43536 KB Output isn't correct
20 Incorrect 338 ms 44816 KB Output isn't correct