Cod sursa(job #3232786)

Utilizator rockoanaOana Pasca rockoana Data 1 iunie 2024 13:07:12
Problema Stergeri Scor 100
Compilator cpp-64 Status done
Runda Simulare E4 #1 Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ft first
#define sd second
using i64 = int64_t;
const i64 INF = 3 * 1e9;

class segtree {
 private:
  vector<i64> data;
  i64 len;

  i64 realLen(i64 n) {
    i64 res = 1;
    while (res <= n) {
      res *= 2;
    }
    return res * 2;
  }

 public:
  segtree(i64 L) {
    len = realLen(L);
    data.assign(len + 1, 0);
  }

  void update(i64 idx, i64 val) {
    idx += len / 2;
    data[idx] += val;
    idx /= 2;
    while (idx > 0) {
      data[idx] = data[idx * 2] + data[idx * 2 + 1];
      idx /= 2;
    }
  }

  i64 query(i64 l, i64 r) {
    l += len / 2;
    r += len / 2;

    i64 res = 0;
    while (l <= r) {
      if (l % 2 == 1) {
        res += data[l];
        l++;
      }

      if (r % 2 == 0) {
        res += data[r];
        r--;
      }

      r /= 2;
      l /= 2;
    }

    return res;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // #ifdef LOCAL
  ifstream cin{"stergeri.in"};
  ofstream cout{"stergeri.out"};
  // #endif

  i64 n, mm, k;
  cin >> n >> mm >> k;

  // set<i64> cc;
  vector<pair<i64, i64>> v(mm);
  for (i64 i = 0; i < mm; i++) {
    cin >> v[i].ft >> v[i].sd;
    // cc.insert(v[i].ft);
    // cc.insert(v[i].sd);
  }

  reverse(v.begin(), v.end());
  i64 res = k;
  for (i64 i = 0; i < mm; i++) {
    if (v[i].ft <= res) {
      res += (v[i].sd - v[i].ft) + 1;
    }
  }
  cout << res;

  // map<i64, i64> m;
  // i64 crt = 1;
  // for (auto& e : cc) {
  //   m[e] = crt;
  //   crt++;
  // }

  // segtree s(crt + 2);
  // for (i64 i = 0; i < mm; i++) {
  //   i64 v1 = s.query(1, m[v[i].ft]) + v[i].ft;
  //   i64 v2 = s.query(1, m[v[i].sd]) + v[i].sd;
  //   s.update(m[v[i].ft], v2 - v1 + 1);
  // }

  // i64 idx = 0;
  // for (auto& e : cc) {
  //   if (e > k) {
  //     break;
  //   }
  //   idx = e;
  // }

  // cout << s.query(1, m[idx]) + k;

  return 0;
}