oj.uz

Submission #109694

# Submission time Handle Problem Language Result Execution time Memory
109694 2019-05-07T13:58:48 Z ffresh None (JOI16_matryoshka) C++17
11 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int R[N],H[N];
void solve() {
   int n,q;
   scanf("%d%d",&n,&q);
   for(int i=0;i<n;++i) {
      scanf("%d%d",&R[i],&H[i]);
   }

   for(int i=0;i<q;++i) {
      vector<pair<int,int> > in;
      int a,b;
      scanf("%d%d",&a,&b);
      for(int j = 0;j<n;++j) {
         if(R[j]>=a && H[j]<=b) {
            in.push_back(make_pair(R[j],H[j]));
         }
      }
      sort(in.begin(),in.end());
      multiset<pair<int,int> >s;
      
      int ret = 0;
      for(int j = 0;j<in.size();++j) {
         s.insert(make_pair(in[j].second,in[j].first));
      }
      for(int j = in.size()-1;j>=0;) {
         int k;
         for(k = j;k>=0;--k) {
            if(in[j].first!= in[k].first) {
               break;
            }
            //cout<<in[k].first<<endl;
            if(s.count(make_pair(in[k].second,in[k].first))){
               ++ret;
               multiset<pair<int,int> > ::iterator it = s.find(make_pair(in[k].second,in[k].first));
               s.erase(it);
            }
         }
         for(k = j;k>=0;--k) {
            if(in[j].first != in[k].first) {
               break;
            }
            int g = in[k].second;
            multiset<pair<int,int> >::iterator it = s.lower_bound(make_pair(g,0));
            if(it != s.begin()) {
               it = prev(it);
               s.erase(it);
            }
         }
         j = k;
      }
      printf("%d\n", ret);
   }
}
int main()
{
    //freopen("input.txt","r",stdin);
    solve();
}

Compilation message

matryoshka.cpp: In function 'void solve()':
matryoshka.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0;j<in.size();++j) {
                     ~^~~~~~~~~~
matryoshka.cpp:9:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&n,&q);
    ~~~~~^~~~~~~~~~~~~~
matryoshka.cpp:11:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d",&R[i],&H[i]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:17:12: 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 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 49.0

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