Submission #251475

#	Time	Username	Problem	Language	Result	Execution time	Memory
251475		casperwang	Lollipop (POI11_liz)	C++14	100 / 100	550 ms	27792 KiB

liz

#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 (stderr)

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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9