oj.uz

Submission #106014

# Submission time Handle Problem Language Result Execution time Memory
106014 2019-04-16T07:58:30 Z MrTEK trapezoid (balkan11_trapezoid) C++14
30 / 100
 311 ms 22128 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;
const int mod = 30013;
const int inf = 1e9;

#define ul first.first
#define ur first.second
#define dl second.first
#define dr second.second

pair <ii,ii> a[N];
int n;
ii ans,dp[N],tree[N << 3];
map <int,int> ind;
vector <int> v,updates[N];

int add(int x,int y) {
  return x + y >= mod ? x + y - mod : x + y;
}

ii merge(ii x,ii y) {
  if (x.first == y.first)
    return {x.first,add(x.second,y.second)};
  if (x.first > y.first)
    return x;
  return y;
}

ii query(int ind,int l,int r,int lw,int rw) {
  if (l > rw || r < lw)
    return {-inf,-inf};
  if (l >= lw && r <= rw)
    return tree[ind];
  int mid = (l + r) / 2;
  return merge(query(ind + ind,l,mid,lw,rw),query(ind + ind + 1,mid + 1,r,lw,rw));
}

void update(int ind,int l,int r,int w,ii val) {
  if (l > w || r < w)
    return;
  if (l == w && r == w) {
    tree[ind] = merge(tree[ind],val);
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind,l,mid,w,val);
  update(ind + ind + 1,mid + 1,r,w,val);
  tree[ind] = merge(tree[ind + ind],tree[ind + ind + 1]);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i].ul >> a[i].ur >> a[i].dl >> a[i].dr;
    v.push_back(a[i].dl);
    v.push_back(a[i].dr);
  }
  sort(v.begin(),v.end());
  for (int i = 0 , j = 0 ; i < v.size() ; i++) {
    if (i == 0 || v[i] != v[i - 1])
      j++;
    ind[v[i]] = j;
  }
  sort(a + 1,a + n + 1);
  for (int i = 1 ; i < (N << 3) ; i++)
    tree[i] = {-inf,-inf};
  for (int i = n , j = n ; i >= 1 ; i--) {
    for (auto k : updates[i])
      update(1,1,2 * n,ind[a[k].dl],dp[k]);
    ii tut = query(1,1,2 * n,ind[a[i].dr] + 1,2 * n);
    tut.first++;
    dp[i] = merge({1,1},tut);
    while(j > 0 && a[j].ur >= a[i].ul)
      j--;
    updates[j].push_back(i);
    ans = merge(ans,dp[i]);
  }
  cout << ans.first << " " << ans.second << endl;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:67:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0 , j = 0 ; i < v.size() ; i++) {
                            ~~^~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8960 KB Output is correct
2 Correct 9 ms 8960 KB Output is correct
3 Incorrect 10 ms 9088 KB Output isn't correct
4 Correct 12 ms 9088 KB Output is correct
5 Incorrect 13 ms 9216 KB Output isn't correct
6 Incorrect 10 ms 9344 KB Output isn't correct
7 Correct 16 ms 9472 KB Output is correct
8 Incorrect 19 ms 9600 KB Output isn't correct
9 Incorrect 29 ms 10360 KB Output isn't correct
10 Correct 43 ms 11612 KB Output is correct
11 Incorrect 56 ms 12280 KB Output isn't correct
12 Incorrect 123 ms 15576 KB Output isn't correct
13 Incorrect 147 ms 16884 KB Output isn't correct
14 Incorrect 197 ms 18160 KB Output isn't correct
15 Incorrect 221 ms 18800 KB Output isn't correct
16 Incorrect 235 ms 19568 KB Output isn't correct
17 Incorrect 239 ms 20084 KB Output isn't correct
18 Correct 178 ms 20840 KB Output is correct
19 Incorrect 232 ms 21360 KB Output isn't correct
20 Incorrect 311 ms 22128 KB Output isn't correct