Submission #20390

#TimeUsernameProblemLanguageResultExecution timeMemory
20390윤지학 (#35)초음속철도 (OJUZ11_rail)C++98
0 / 100
3 ms29244 KiB
#include <cstdio> #include <algorithm> using namespace std; const int P = 1000000007; pair<int, int> a[200002]; int t[400004]; struct tree { tree *l, *r; int s, e, x, y; } T[800008]; int Tn; void Init(tree *p, int s, int e) { p->s = s; p->e = e; p->x = s == 1 && e == 1; p->y = 1; if (s != e) { Init(p->l = T + ++Tn, s, s + e >> 1); Init(p->r = T + ++Tn, (s + e >> 1) + 1, e); } } void Lazy(tree *p) { p->l->x = ((long long)p->l->x * p->y + p->x) % P; p->l->y = (long long)p->l->y * p->y % P; p->r->x = ((long long)p->r->x * p->y + p->x) % P; p->r->y = (long long)p->r->y * p->y % P; p->y = 1; p->x = 0; } void Mul(tree *p, int e) { if (p->s > e) return; if (p->e == e) { p->x = (p->x << 1) % P; p->y = (p->y << 1) % P; return; } Lazy(p); Mul(p->l, e); Mul(p->r, e); } void Add(tree *p, int s, int e, int x) { if (p->s > e || p->e < s) return; if (s <= p->s && p->e <= e) { p->x = (p->x + x) % P; return; } Lazy(p); Add(p->l, s, e, x); Add(p->r, s, e, x); } int Get(tree *p, int x) { if (p->s == x && p->e == x) return p->x; Lazy(p); return p->r->s > x ? Get(p->l, x) : Get(p->r, x); } int main() { int i, j, k, n, m, r = 0; scanf("%d%d", &t[1], &n); if (n > 5000) return 0; t[0] = 1; for (i = 1; i <= n; i++) { scanf("%d%d", &t[i << 1], &t[i << 1 | 1]); a[i].first = t[i << 1 | 1]; a[i].second = -t[i << 1]; } sort(a + 1, a + n + 1); sort(t, t + n + n + 2); m = unique(t, t + n + n + 2) - t; Init(T, 1, m); for (i = 1; i <= n; i++) { a[i].first = upper_bound(t, t + m, a[i].first) - t; a[i].second = upper_bound(t, t + m, -a[i].second) - t; k = Get(T, a[i].second); if (a[i].first == m) r = (r + k) % P; Mul(T, a[i].second - 1); Add(T, a[i].second, a[i].first, k); } printf("%d", r); }

Compilation message (stderr)

rail.cpp: In function 'void Init(tree*, int, int)':
rail.cpp:23:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Init(p->l = T + ++Tn, s, s + e >> 1);
                              ^
rail.cpp:24:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Init(p->r = T + ++Tn, (s + e >> 1) + 1, e);
                            ^
rail.cpp: In function 'int main()':
rail.cpp:67:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, n, m, r = 0;
         ^
rail.cpp:68:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &t[1], &n);
                          ^
rail.cpp:72:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &t[i << 1], &t[i << 1 | 1]);
                                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...