oj.uz

Submission #251475

# Submission time Handle Problem Language Result Execution time Memory
251475 2020-07-21T10:52:13 Z casperwang Lollipop (POI11_liz) C++14
100 / 100
 550 ms 27792 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000000;
int n, q;
int k, l, r;
int L, R;
string s;
int a[MAXN+1];
int pre[MAXN+1];
int suf[MAXN+2];

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  cin >> s;
  for (int i = 0; i < s.size(); i++)
    a[i+1] = (s[i] == 'T' ? 2 : 1);
  for (int i = 1; i <= n; i++)
    pre[i] = pre[i-1] + a[i], R = (a[i] == 1 ? i : R);
  for (int i = n; i >= 1; i--)
    suf[n-i+1] = suf[n-i] + a[i], L = (a[i] == 1 ? n-i+1 : L);
  for (int i = 0; i < q; i++) {
    cin >> k;
    if (pre[R] >= k) {
      l = lower_bound(pre, pre+n+1, pre[R]-k) - pre;
      if (pre[R] - pre[l] < k) l--;
      r = (pre[R] - pre[l] == k ? R : R-1);
      l++;
      cout << l << " " << r << "\n";
    } else if (suf[L] >= k) {
      r = lower_bound(suf, suf+n+1, suf[L]-k) - suf;
      if (suf[L] - suf[r] < k) r--;
      l = (suf[L] - suf[r] == k ? L : L-1);
      r++;
      cout << n+1-l << " " << n+1-r << "\n";
    } else if (pre[n] < k) {
      cout << "NIE\n";
    } else {
      l = lower_bound(pre, pre+n+1, pre[n]-k) - pre;
      if (pre[n] - pre[l] != k)
        cout << "NIE\n";
      else
        cout << l+1 << " " << n << "\n";
    }
  }
}

Compilation message

liz.cpp: In function 'int main()':
liz.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++)
                   ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 896 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 38 ms 1712 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2040 KB Output is correct
2 Correct 154 ms 5860 KB Output is correct
3 Correct 81 ms 3192 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2168 KB Output is correct
2 Correct 30 ms 2172 KB Output is correct
3 Correct 77 ms 3576 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 5368 KB Output is correct
2 Correct 126 ms 4728 KB Output is correct
3 Correct 160 ms 6660 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 12172 KB Output is correct
2 Correct 281 ms 11916 KB Output is correct
3 Correct 320 ms 14088 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 13708 KB Output is correct
2 Correct 327 ms 16652 KB Output is correct
3 Correct 351 ms 16784 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 25896 KB Output is correct
2 Correct 434 ms 24084 KB Output is correct
3 Correct 451 ms 22164 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 26768 KB Output is correct
2 Correct 525 ms 27792 KB Output is correct
3 Correct 381 ms 26384 KB Output is correct