oj.uz

Submission #106013

# Submission time Handle Problem Language Result Execution time Memory
106013 2019-04-16T07:53:49 Z MrTEK trapezoid (balkan11_trapezoid) C++14
30 / 100
 257 ms 22000 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]);    
    dp[i] = {1,1};
    ii tut = query(1,1,2 * n,ind[a[i].dr],2 * n);
    tut.first++;
    dp[i] = merge(dp[i],tut);
    while(j > 0 && a[j].ur >= a[i].ul)
      j--;
    ans = merge(ans,dp[i]);
    updates[j].push_back(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 9088 KB Output is correct
2 Correct 9 ms 8960 KB Output is correct
3 Incorrect 10 ms 8960 KB Output isn't correct
4 Correct 10 ms 9088 KB Output is correct
5 Incorrect 12 ms 9216 KB Output isn't correct
6 Incorrect 15 ms 9316 KB Output isn't correct
7 Correct 19 ms 9472 KB Output is correct
8 Incorrect 16 ms 9600 KB Output isn't correct
9 Incorrect 29 ms 10368 KB Output isn't correct
10 Correct 48 ms 11640 KB Output is correct
11 Incorrect 60 ms 12280 KB Output isn't correct
12 Incorrect 111 ms 15600 KB Output isn't correct
13 Incorrect 141 ms 16884 KB Output isn't correct
14 Incorrect 187 ms 18160 KB Output isn't correct
15 Incorrect 203 ms 18796 KB Output isn't correct
16 Incorrect 229 ms 19460 KB Output isn't correct
17 Incorrect 224 ms 20200 KB Output isn't correct
18 Correct 187 ms 20892 KB Output is correct
19 Incorrect 220 ms 21408 KB Output isn't correct
20 Incorrect 257 ms 22000 KB Output isn't correct