/**
* This is solution for problem not-equal-segments
* This is nk_ok.cpp
*
* @author: Nikolay Kalinin
* @date: Thu, 01 Mar 2018 21:12:52 +0300
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
const int MOD = 1000'000'007;
struct tev
{
int x, from, type;
};
inline bool operator<(const tev &a, const tev &b)
{
return a.x < b.x;
}
vector<tev> events;
vector<pair2<int>> dp0, dp1;
int k, n, m;
inline int powmod(int a, int b)
{
int tmp = a;
int ans = 1;
while (b)
{
if (b & 1) ans = ((ll)ans * tmp) % MOD;
tmp = ((ll)tmp * tmp) % MOD;
b >>= 1;
}
return ans;
}
inline int get(int x)
{
return (powmod(2, x) - 1 + MOD) % MOD;
}
int main()
{
scanf("%d%d%d", &k, &n, &m);
for (int i = 0; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
a--, b--;
events.pb({a - 1, -1, -1});
events.pb({b, a, 0});
}
for (int i = 0; i < m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
a--, b--;
events.pb({a - 1, -1, -1});
events.pb({b, a, 1});
}
events.pb({k - 1, -1, -1});
sort(all(events));
int last = -1;
dp0.push_back({-1, 1});
int cur0 = 0;
int sum0 = 1;
dp1.push_back({-1, 0});
int cur1 = 0;
int sum1 = 0;
for (auto t : events)
{
if (t.x > last)
{
dp1.back().se = (dp1.back().se + sum0) % MOD;
dp0.back().se = (dp0.back().se + sum1) % MOD;
dp1.pb({t.x, (ll)get(t.x - last - 1) * (sum0 + sum1) % MOD});
dp0.pb(dp1.back());
int newsum0 = ((ll)sum0 + sum1 + dp0.back().se) % MOD;
int newsum1 = ((ll)sum0 + sum1 + dp1.back().se) % MOD;
sum0 = newsum0;
sum1 = newsum1;
}
if (t.type == 0)
{
while (cur1 < (int)dp1.size() && dp1[cur1].fi < t.from)
{
sum1 = (sum1 - dp1[cur1].se + MOD) % MOD;
cur1++;
}
}
if (t.type == 1)
{
while (cur0 < (int)dp0.size() && dp0[cur0].fi < t.from)
{
sum0 = (sum0 - dp0[cur0].se + MOD) % MOD;
cur0++;
}
}
last = t.x;
}
cout << (sum0 + sum1) % MOD << endl;
return 0;
}
Oh plz, where's the tutorial for div1 E?
Isn't it 944D — Game with String?
No, It's the problem "Coins Exhibition"
http://codeforces.com/problemset/problem/930/E
Or Problem 944G — Coins Exhibition
http://codeforces.com/contest/944/problem/D
I know this problem. It's Div1 B or Div2 E, not Div1 E.
Are there other problems similar to 944D — Game with String? It is a very interesting problem and I want to practice it more. Thanks
Is Div. 1 D solvable by some kind of modified convex hull algorithm?
I think the method mentioned by the tutorial, is just some kind of modified convex hull algorithm.
Can someone explain Div.2C?
Say you have only 0's, 1's and 2's in array.
To preserve average you can either pick 0 and 2 and change both to 1 or pick two 1's and change one of them to 0 and other one to 2. Obviously, it makes no sense to take 0, 2 change it to two 1's and then change it back to 0 and 2 again, you won't gain anything.
So now you pick one of the transformations 0,2 into 1,1 or 1,1 into 0,2. Pick one that gives you more numbers to change and perform transformations.
Example:
0 0 0 1 1 1 2 2 2 2 2
Here, you can pick two 1's and get the array:
0 0 0 0 1 2 2 2 2 2 2
but that way you changed only 2 numbers. It's better to pick 0's and 2's, change them into 1's so you will get:
1 1 1 1 1 1 1 1 1 2 2
(notice how you have to left 2's at the end since you don't have more 0's to "balance" the change in terms of average value).
For the next paragraph I will use this definition: cnt(x) — number of times x is present in array
How many changes will you get from transforming 0's and 2's into 1's? min(cnt(0), cnt(2)) * 2
How many changes will you get from transforming 1's into 0's and 2's? floor(cnt(1) / 2) * 2 (fancy way of saying cnt(1) if cnt(1) is even and cnt(1) — 1 if it's odd)
Special cases:
1) There are only 0's in array; there are only 0's and 1's in array — in those cases you cannot change anything (remember about the constraint that your minimal/maximal numbers have to be between minimal/maximal from original array, so you don't have any possibility for change without breaking this constraint or changing average). Obviously the same case for only 1's etc.
2) There are 0's and 2's in array — that just reduces to transforming as many of them as you can into 1's.
My solution:
http://codeforces.com/contest/931/submission/35947027
(it's not crystal clear, because of the part which actually changes the numbers in array, I guess I should have done it in different way)
Thanks for your comment ! I too was following your approach and not the editorial one and was not able to debug until I came across your post. I missed the special cases !
Here is my code and explanation
Case1 : (xMax-xMin)<2
Case 2 : (xMax-xMin)==2
Suppose xMax = a+1, then xMin = a-1 and the other number whose presence is not guranteed will be 'a'. So there are two ways,
Way 1 — You replace a+1 and a-1 with 2 a, because sum will remain same.
Way 2 — You replace 2 a with a+1 and a-1, in this case also sum will remain same.
The most optimal way to get answer will be to follow one way at all steps, because there is no sense of replacing 2 a with a+1 and a-1, and then again replacing a+1 and a-1 with a.
Now you just have to check which way, either 1 or 2 is more optimal.
I'm wondering why there's still no tuturials for the problem Coins Exhibition. I got stuck on this problem and need help.....
Problem A video solution: https://youtu.be/bFEmX3y8idE Problem B video solution: https://youtu.be/tzF_nagpR5A
Problem C and D coming
so where is the solution of div1.E?`
Is the formula in a 944B problem for finding the number of (min + 1)s is correct? // leftSum — minSum ?
KAN Excuse me, sir?
Hello everyone.
For the problem 944 E, my code gets WA at test case 3.
This is my code- http://codeforces.com/contest/930/submission/38547479
I would like to know the error in my code.
For every index i, I'm taking the sum of longest non-decreasing subsequence ending at i, and the longest non-increasing subsequence starting at i, minus 1.
In 931D - Peculiar apple-tree Here's how the tree looks for the second sample test case
For 944C: many accepted Solutions from others Fail this Test Case
INput: 6 -2 2 2 0 0 -2
OUTput (from other's accepted code): 2 0 0 0 0 0 0
But the actual answer is : 0 -1 -1 -1 1 1 1