oj.uz

Submission #172749

# Submission time Handle Problem Language Result Execution time Memory
172749 2020-01-02T14:13:56 Z arnold518 None (JOI16_matryoshka) C++14
11 / 100
 2 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct Point
{
    int x, y;
};

int N, Q;
Point A[MAXN+10];

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y);

    sort(A+1, A+N+1, [&](const Point &p, const Point &q)
         {
             if(p.x!=q.x) return p.x<q.x;
             return p.y<q.y;
         });

    vector<Point> V;

    multimap<int, int> S;
    for(i=1; i<=N; )
    {
        for(j=i; j<=N && A[j].x==A[i].x; j++)
        {
            auto it = S.lower_bound(A[j].y);
            if(it==S.begin()) continue;
            it--;
            V.push_back({it->second, A[j].y});
            S.erase(it);
        }
        for(j=i; j<=N && A[j].x==A[i].x; j++)
        {
            S.insert(pii(A[j].y, A[j].x));
        }
        i=j;
    }

    while(Q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int ans=0;
        for(j=1; j<=N; j++) if(A[j].x>=a && A[j].y<=b) ans++;
        for(j=0; j<V.size(); j++) if(V[j].x>=a && V[j].y<=b) ans--;
        printf("%d\n", ans);
    }
}

Compilation message

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<V.size(); j++) if(V[j].x>=a && V[j].y<=b) ans--;
                  ~^~~~~~~~~
matryoshka.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
matryoshka.cpp:23:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -