fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define clr(x) memset((x), 0, sizeof(x))
  3. #define all(x) (x).begin(), (x).end()
  4. #define pb push_back
  5. #define mp make_pair
  6. #define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
  7. #define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
  8. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  9. #define ford(i, n) for(int i=(n)-1; i>=0; i--)
  10. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  11. #define in(x) int (x); input((x));
  12. #define x first
  13. #define y second
  14. #define less(a,b) ((a) < (b) - EPS)
  15. #define more(a,b) ((a) > (b) + EPS)
  16. #define eq(a,b) (fabs((a) - (b)) < EPS)
  17. #define remax(a, b) ((a) = (b) > (a) ? (b) : (a))
  18. #define remin(a, b) ((a) = (b) < (a) ? (b) : (a))
  19. using namespace std;
  20. typedef long double ld; template <class _T> inline _T sqr(const _T& x) {return x * x;} template <class _T> inline string tostr(const _T& a) {ostringstream os(""); os << a; return os.str();} const ld PI = 3.1415926535897932384626433832795L; const ld EPS = 5e-12; char TEMPORARY_CHAR; typedef long long ll; typedef unsigned long long ull; typedef set < int > SI; typedef vector < int > VI; typedef vector < vector < int > > VVI; typedef map < string, int > MSI; typedef pair < int, int > PII; const int INF = 1e9; inline void input(int &a) {a = 0; while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') && (TEMPORARY_CHAR != '-')){} char neg = 0; if (TEMPORARY_CHAR == '-') {neg = 1; TEMPORARY_CHAR = getchar();} while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {a = 10 * a + TEMPORARY_CHAR - '0'; TEMPORARY_CHAR = getchar();} if (neg) a = -a;} inline void out(int a) {if (!a) putchar('0'); if (a < 0) {putchar('-'); a = -a;} char s[10]; int i; for(i = 0; a; ++i) {s[i] = '0' + a % 10; a /= 10;} ford(j, i) putchar(s[j]);} inline int nxt() {in(ret); return ret;}
  21.  
  22. int main()
  23. {
  24.     in(N); in(q); in(M);
  25.     int a[N + 1];
  26.     for(int i = 1; i <= N; ++i)
  27.         a[i] = nxt();
  28.     int log_N = 0;
  29. 	while ((1 << log_N) < N)
  30. 	    log_N++;
  31.     int ans[N + 1][log_N + 1];
  32. 	for(int i = 0; i <= log_N; ++i)
  33. 		ans[0][i] = 1;
  34. 	int i = 1;
  35. 	int sum = 0;
  36. 	for(int j = 1; j <= N; ++j)
  37. 	{
  38. 		sum += a[j];
  39. 		while(sum > M)
  40. 			sum -= a[i++];
  41. 		ans[j][0] = i;
  42. 		for(int l = 1; l <= log_N; ++l)
  43. 			ans[j][l] = ans[ans[j][l - 1] - 1][l - 1];
  44. 	}
  45. 	while(q--)
  46. 	{
  47. 	    in(u); in(v);
  48. 	    int p = 0;
  49. 	    if (v >= u)
  50. 	    {
  51. 	        puts("1");
  52. 	        continue;
  53. 	    }
  54. 	    while(v)
  55. 	    {
  56. 	        if (v & 1)
  57. 	            u = ans[u][p] - 1;
  58. 	        ++p;
  59. 	        v >>= 1;
  60. 	    }
  61. 	    out(u + 1);
  62. 	    puts("");
  63. 	}
  64. 	return 0;
  65. }
  66.  
Time limit exceeded #stdin #stdout 5s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KSgMhE
language:
C++ (gcc 8.3)
created:
12 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!