Just checked your solution, you had it synced with stdio (it is synced by default). If you add the following line to the beginning of your code, it should give AC: cin.sync_with_stdio(false);

I think the AC solutions with cin did not have it synced with stdio, which makes it faster. Still, whenever the input is larger than 2 x 10^5, I don't think it is a good idea to use cin (even without syncing it with stdio).

I believe it is expected of contestants to know when to use fast input (10^6 numbers takes a lot of time to read using cin)

even though you check for the bounds, you still search the whole string. Think of the case when the string is 10^5 characters long and starts with a '*'. And you have 10^5 queries of single character. For each query, you will run through the whole 10^5 string, because even though you check the sizes, you never break when you should. Thus, 10^5 x 10^5, TLE.

TrueLove You don't need to pass through every node on the path to the LCA, you can precalculate with a dp and find it in O(log n)

yeah I thought about LCA but my solution was giving WA in pretest 6... I can't see why it wouldn't work -- fix a station A, get the LCA between B and C (call it L). If L equals A, the answer is 1. If L is either B or C, the answer is the minimum distance (A, B) or (A, C). Otherwise, the answer is the distance (A, L). I even permuted A, B, and C to get all possible combinations since the LCA runs fast. Why is that incorrect?

that shouldn't keep you from coding your O(n) solution since reading will always take O(n)... So if you had 10^5 string with size 10^5, the problemsetter would already have to set a high time limit just for reading, which would allow you to solve the problem in the expected O(n) way...

well, then it would have been found on an early iteration. I always take the fountain i with the fountain returned by the query. If the best fountain to pair with i (let's call it j) is before i itself, then in the iteration of j the query would have returned i.

Can someone tell me why my approach for C is wrong?

First, I try to match 1 fountain of C with 1 fountain of D. In that case it will be the most beautiful of each one that I can afford. The other case is to get 2 fountains of C or 2 fountains of D.

So I sort them by cost, and build a segment tree of maximum beauty within range. Then, for each fountain, I take its cost and binary search the most expensive fountain that I can afford (which will give me an index j in the array the segment tree was based on). Then I just query the segment tree for the range (i+1, j). Then take the maximum of every iteration on both types.

Code: https://ghostbin.com/paste/ogevq

Wrong Answer on pretest 4.

well most of them informed that if there were multiple solutions you could print any.

when you're dealing with string as a char array, it does.

Is it just me or recently in div 2 rounds the difficulty gap between problems is getting larger?

I see, so it doesn't give RE only because that memory region is luckily located within the program scope. Well, at least it didn't pass the systest. Thanks for the clarification, it was very helpful!

no it isn't

Ricks and Mortys have registered online in these groups. So, a person can have joined a group more than once (developer of this website hadn't considered this possibility).

sure: submission

it received WA on systest, but I was wondering why the hack didn't pass

pretty balanced

on div2b, why no runtime error for negative values on this solution?

Unsuccessful Hack case

10000 2
8 1 -1 -1000 -2000 -3000 -4000 -5000 -6000
8 1 -1 -1000 -2000 -3000 -4000 -5000 -7000

Divide n by 2 until it is 0 and put that in an array in ascending order.

You can see a pattern generated by the number and the final set.

Take the index of one 1/0 in the list. Then take the highest power of two that divides that index. The expoent of the power will be exactly the index of the corresponding number that generated it in the array that we built. Therefore, if the number in the array is even, it will be 0, if it is odd, it will be 1.

Thus, we can just iterate from l to r, checking the powers of two, and adding 1 or 0 to a counter according to the prebuilt array.

i.e. suppose n is 17

the array built will be 1 2 4 8 17

suppose l is 12 and r is 16

12 is divided by 4, which is 2^2, the index 2 in the array is 4, which is even, so the position 12 in the list is 0

13 is divided by 1 which is 2^0, the index 0 in the array is 1, which is odd, so the position 13 in the list is 1

14 is divided by 2 which is 2^1, the index 1 in the array is 2, which is even, so the position 14 in the list is 0

15 gives the same as 13 (and actually every odd index)

16 is divided by 16 which is 2^4, the index 4 in the array is 17, which is odd, so the position 16 in the list is 1 and so on.

I find that this is the simplest way to solve the problem (my solution was 17 lines long). Unfortunately my solution received Runtime Error because I forgot to test when n = 0.

Expected complexity O(log N + 50 * (R — L))

int main(){
	ll n, l, r, cont = 0;
	cin >> n >> l >> r;
	if(n == 0) {
		cout << 0 << endl;
		return 0;
	}
	vector<ll> fac;
	for(ll i = n; i; (i >>= 1)){
		fac.pb(i);
	}
	reverse(fac.begin(),fac.end());
	for(ll i = l; i <= r; i++){
		int e;
		for(e = 51; e >= 0; e--){
			if(i%(1LL<<e) == 0) break;
		}
		cont += (fac[e]&1);
	}
	cout << cont << endl;
	return 0;
}

multiple 502 Bad Gateway issues when trying to submit solutions really screwed my time penalty :/

GabrielTaets appreciates the information.

because 4 is not prime. You check for n-2 because 2 is also prime, and then that odd number would be written as a sum of 2 primes. if you checked for n-4, then you would decompose the number in one prime plus 4, which would give 3 instead. The only case that an odd number is a sum of two primes, is when one of them is 2.

yeah, just found out it gives WA for 2e9 as input :/ fml

That sad moment when you're certain of your solution but it won't pass and you can't find where is the error

rip rating :/

i always thought that if you had already read a problem, you'd be rated. well, good to know, thanks!

if you entered the contest area, you will get a rating.

just understand that if they change "a few hours" to benefit "you", there will be people that will still be upset about the time. Simply there is just no way to please everyone simultaneously. If you can't participate at this time, just wait for a round that suits you better, it's not like there are rounds only once a month.

will there be an editorial?

Great timing! Wish everyone many accepted solutions, and happy birthday BigBag :)

and it collides with icpc first phase in south america :(

Oh now I won't be able to participate anymore :( sadlife

First, the input for which your answer was wrong is not "cAPSlock", it is "cAPSlOCK". The difference is that there is a lowercase 'l' between two uppercase substrings, which breaks your code:

		bool change=false;
		for (int i=1; i<str.length(); ++i) {
			if (str.at(i)-96 < 0) {
				change=true;
				for (int j=i; j<str.length(); ++j)
					if (str.at(j)-96 > 0) {
						change=false;
					}
			}
		}

Note that you scan the string looking for an uppercase character. When you find one, you set the flag as true, and then scan the remaining string for a lowercase character. Then, if you find a lowercase character, you reset the flag to false. The problem is, you continue to scan the string. And when you do this, you "undo" what you had done in the previous iteration (you "forget" what you saw). Another thing you code does wrong: when the change flag is true, you set the first character to uppercase and the rest to lowercase, which is not what the problem asks you to do. It asks you to change every character case. So if the string is completely uppercase, the result should be completely lowercase. What I advise you to do: think of a different way to check whether the string matches the restriction or not. You don't need to iterate through it twice as your code does. You can set a flag as true, and iterate through it only once, starting at position 1. If you happen to see a lowercase character, set the flag as false. At the end of the loop, if your flag is still true, it means there wasn't any lowercase characters — so you are allowed to flip the casing. If the flag is false, then there was at least one lowercase character in the middle — then you shouldn't do anything. Here is my answer for this problem:

#include <bits/stdc++.h>
using namespace std;

int main(){
  string str;
  cin >> str;
  bool flag = true;
  for(int i = 1; i < str.size() && flag; i++){
    if(str[i] > 'Z') flag = false;
  }
  if(flag){
    for(int i = 0; i < str.size(); i++){
      str[i] = (str[i] == tolower(str[i]) ? toupper(str[i]) : tolower(str[i]));
    }
  }
  cout << str << endl;
  return 0;
}

Me too, TLE with O(2*N)... :/

so... i don't know about you, but I just hit my face :c

if you want to keep mid as a global variable, you have to reassign it after the first recursion so it has the correct value again.

int mid;
void run(int l,int r)
{
    if(l==r) ;
    else
    {
        mid=(l+r)/2;
        cout<<mid<<endl;
        run(l,mid); // after this runs, mid will have a different value
        mid=(l+r)/2; // reset the value before the next recursion
        run(mid+1,r);
    }
}