fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define clr(x) memset((x), 0, sizeof(x))
  4. #define all(x) (x).begin(), (x).end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define in(x) int (x); input((x));
  8. #define x first
  9. #define y second
  10. #define forn(i, n) for(int i = 0; i < (int)(n); ++i)
  11. #define ford(i, n) for(int i = (int)(n) - 1; i >= 0; --i)
  12. #define for1(i, n) for(int i = 1; i <= (int)(n); ++i)
  13.  
  14. typedef int itn;
  15.  
  16. #define next next12345
  17. #define prev prev12345
  18. #define left lefdsf232
  19. #define right rig43783
  20. #define x1 x12345
  21. #define y1 y12345
  22.  
  23. using namespace std;
  24.  
  25. template<typename T>
  26. T gcd(T x, T y) {
  27.     while (y > 0) {
  28.         x %= y;
  29.         swap(x, y);
  30.     }
  31.     return x;
  32. }
  33.  
  34. template<class T>
  35. T lcm(T a, T b) {
  36.     return a / gcd(a, b) * b;
  37. }
  38.  
  39.  
  40. template<class _T>
  41. inline _T sqr(const _T &x) {
  42.     return x * x;
  43. }
  44.  
  45. template<class _T>
  46. inline string tostr(const _T &a) {
  47.     ostringstream os("");
  48.     os << a;
  49.     return os.str();
  50. }
  51.  
  52. typedef long double ld;
  53. typedef long long ll;
  54. typedef unsigned long long ull;
  55. typedef pair<int, int> PII;
  56. const ld PI = 3.1415926535897932384626433832795L;
  57.  
  58. template<typename T>
  59. inline void input(T &a) {
  60.     static int ed;
  61.     a = 0;
  62.     while (!isdigit(ed = getchar()) && ed != '-') { }
  63.     char neg = 0;
  64.     if (ed == '-') {
  65.         neg = 1;
  66.         ed = getchar();
  67.     }
  68.     while (isdigit(ed)) {
  69.         a = 10 * a + ed - '0';
  70.         ed = getchar();
  71.     }
  72.     if (neg) a = -a;
  73. }
  74.  
  75. template<typename T = int>
  76. inline T nxt() {
  77.     T res;
  78.     input(res);
  79.     return res;
  80. }
  81.  
  82. void myassert(bool v) {
  83.     assert(v);
  84.     //cout << "FAIL\n";
  85.     //exit(0);
  86. }
  87.  
  88. mt19937 generator;
  89.  
  90. bool check(int v) {
  91.     if (v < 2) return false;
  92.     for (int i = 2; i * i <= v; ++i) {
  93.         if (v % i == 0) {
  94.             return false;
  95.         }
  96.     }
  97.     return true;
  98. }
  99.  
  100. long long pw(long long a, long long n, long long m) {
  101.     ll res = 1;
  102.     while (n) {
  103.         if (n & 1ll) {
  104.             res = res * a % m;
  105.         }
  106.         a = a * a % m;
  107.         n >>= 1;
  108.     }
  109.     return res;
  110. }
  111.  
  112. long long inv(long long a, long long p) {
  113.     long long res = 1;
  114.     while (a > 1) {
  115.         res = res * (p - p / a) % p;
  116.         a = p % a;
  117.     }
  118.     return res;
  119. }
  120.  
  121. struct F {
  122.     vector <int> a;
  123.  
  124.     F(int n) {
  125.         a.resize(n);
  126.     }
  127.  
  128.     int get(int r) {
  129.         int res = 0;
  130.         for (; r >= 0; r &= r + 1, --r) {
  131.             res += a[r];
  132.         }
  133.         return res;
  134.     }
  135.  
  136.     void inc(int r) {
  137.         for (; r < a.size(); r |= r + 1)
  138.             a[r] += 1;
  139.     }
  140. };
  141.  
  142. bool uax(int &x, int y) {
  143.     if (y > x) {
  144.         x = y;
  145.         return true;
  146.     }
  147.     return false;
  148. }
  149.  
  150. bool uin(int &x, int y) {
  151.     if (y < x) {
  152.         x = y;
  153.         return true;
  154.     }
  155.     return false;
  156. }
  157.  
  158.  
  159. struct vertex {
  160.     vertex * l, * r;
  161.     ll sum;
  162.  
  163.     vertex (ll val)
  164.             : l(NULL), r(NULL), sum(val)
  165.     { }
  166.  
  167.     vertex (vertex * l, vertex * r)
  168.             : l(l), r(r), sum(0)
  169.     {
  170.         if (l)  sum += l->sum;
  171.         if (r)  sum += r->sum;
  172.     }
  173. };
  174.  
  175. vertex * build (int tl, int tr) {
  176.     if (tr - tl == 1)
  177.         return new vertex (0ll);
  178.     int tm = (tl + tr) / 2;
  179.     return new vertex (
  180.             build (tl, tm),
  181.             build (tm, tr)
  182.     );
  183. }
  184.  
  185. ll get_sum (vertex * t, int tl, int tr, int l, int r) {
  186.     if (l >= r)
  187.         return 0;
  188.     if (l == tl && tr == r)
  189.         return t->sum;
  190.     int tm = (tl + tr) / 2;
  191.     return get_sum (t->l, tl, tm, l, min(r,tm))
  192.            + get_sum (t->r, tm, tr, max(l,tm), r);
  193. }
  194.  
  195. vertex * update (vertex * t, int tl, int tr, int pos, int new_val) {
  196.     if (tr - tl == 1)
  197.         return new vertex (new_val + t->sum);
  198.     int tm = (tl + tr) / 2;
  199.     if (pos < tm)
  200.         return new vertex (
  201.                 update (t->l, tl, tm, pos, new_val),
  202.                 t->r
  203.         );
  204.     else
  205.         return new vertex (
  206.                 t->l,
  207.                 update (t->r, tm, tr, pos, new_val)
  208.         );
  209. }
  210.  
  211.  
  212.  
  213. void solve(int test) {
  214.     int n = nxt();
  215.     int m = nxt();
  216.  
  217.     int a[n];
  218.     int b[n + 1];
  219.     forn(i, n) {
  220.         a[i] = nxt();
  221.         b[i] = a[i];
  222.     }
  223.     b[n] = 1;
  224.     sort(b, b + n + 1);
  225.  
  226.     int s = unique(b, b + n + 1) - b;
  227.  
  228.     vertex * data[n + 1];
  229.     data[0] = build(0, s);
  230.  
  231.     for (int i = 0; i < n; ++i) {
  232.         int pos = lower_bound(b, b + s, a[i]) - b;
  233.         data[i + 1] = update(data[i], 0, s, pos, b[pos]);
  234.     }
  235.  
  236. //    cerr << get_sum(data[n], 0, s, 0, 1) - get_sum(data[0], 0, s, 0, 1) << endl;
  237.  
  238.     while (m--) {
  239.         int l = nxt() - 1;
  240.         int r = nxt();
  241.  
  242.         int prev = 0;
  243.         ll sum = 0;
  244.         while (true) {
  245.             int pos = upper_bound(b, b + s, min(sum + 1, 1ll * INT_MAX)) - b;
  246.             if (pos == prev) {
  247.                 break;
  248.             }
  249.             sum = get_sum(data[r], 0, s, prev, pos) - get_sum(data[l], 0, s, prev, pos);
  250.             prev = pos;
  251.         }
  252.  
  253.         cout << sum + 1 << "\n";
  254.     }
  255. }
  256.  
  257.  
  258. int main(int argc, char ** argv) {
  259.  
  260. #ifdef LOCAL
  261.     freopen("input.txt", "r", stdin);
  262. //    freopen("output.txt", "w", stdout);
  263. #else
  264.     #define fname "sequence"
  265.     //freopen(fname".in", "r", stdin);
  266.     //freopen(fname".out", "w", stdout);
  267. #endif
  268.     //ios_base::sync_with_stdio(false);
  269. //    pre();
  270. //    test();
  271. //    exit(0);
  272.     int t = 1;
  273.  
  274. #ifdef LOCAL
  275. #else
  276. #endif
  277.     int c = 0;
  278.  
  279.     while (t--) {
  280.         solve(++c);
  281.     }
  282.  
  283. #ifdef LOCAL
  284.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  285. #endif
  286.     return 0;
  287. }
Time limit exceeded #stdin #stdout 5s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aDgzQl
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!