oj.uz

Submission #106022

# Submission time Handle Problem Language Result Execution time Memory
106022 2019-04-16T08:11:30 Z MrTEK trapezoid (balkan11_trapezoid) C++14
100 / 100
 303 ms 20764 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 <ii> ep;
vector <int> v;

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);
    ep.push_back({a[i].ur,i});
    ep.push_back({a[i].ul,i});
  }
  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;
  }
  for (int i = 1 ; i < (N << 3) ; i++)
    tree[i] = {-inf,-inf};
  sort(ep.begin(),ep.end(),greater<ii>());
  for (auto i : ep) {
    if (a[i.second].ul == i.first)
      update(1,1,2 * n,ind[a[i.second].dl],dp[i.second]);
    else {
      ii tut = query(1,1,2 * n,ind[a[i.second].dr] + 1,2 * n);
      tut.first++;
      dp[i.second] = merge({1,1},tut);
      ans = merge(ans,dp[i.second]);
    }
  }
  cout << ans.first << " " << ans.second << endl;
}

Compilation message

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6656 KB Output is correct
2 Correct 7 ms 6656 KB Output is correct
3 Correct 8 ms 6656 KB Output is correct
4 Correct 8 ms 6784 KB Output is correct
5 Correct 11 ms 6912 KB Output is correct
6 Correct 15 ms 7040 KB Output is correct
7 Correct 14 ms 7168 KB Output is correct
8 Correct 21 ms 7356 KB Output is correct
9 Correct 26 ms 8068 KB Output is correct
10 Correct 43 ms 9556 KB Output is correct
11 Correct 68 ms 10096 KB Output is correct
12 Correct 123 ms 13636 KB Output is correct
13 Correct 148 ms 15076 KB Output is correct
14 Correct 189 ms 16556 KB Output is correct
15 Correct 247 ms 17188 KB Output is correct
16 Correct 248 ms 17924 KB Output is correct
17 Correct 250 ms 18660 KB Output is correct
18 Correct 168 ms 19292 KB Output is correct
19 Correct 244 ms 19972 KB Output is correct
20 Correct 303 ms 20764 KB Output is correct