Saratov State University :: Online Contester


::Go
- home
- news
- register
- update personal info
- problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- links
- projects

::Poll
Are you registered on Codeforces?
Yes
No
What is it???

[results]

::webboard

WA on test 12
Author: SoroushE
ID: 053269
Problem: 311
Contest: 0
Date: 2013-12-19 00:14:29

I get WA on test 12, but I cannot find a bug in my code nor my algorithm nor a test case to produce a wrong answer.
I would appreciate any kind of help :)



#include <iostream>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, pii> plp;

const int MAXN = 1000 * 1000 + 10;
ll sum[MAXN * 4];
int cnt[MAXN * 4];

void shift(int cur)
{
if (cnt[cur] == 0)
{
cnt[cur * 2] = cnt[cur * 2 + 1] = 0;
sum[cur * 2] = sum[cur * 2 + 1] = 0ll;
}
}

void merge(int cur)
{
sum[cur] = sum[cur * 2] + sum[cur * 2 + 1];
cnt[cur] = cnt[cur * 2] + cnt[cur * 2 + 1];
}

void add(int plc, int val, int cur, int s, int e)
{
if (e - s < 2)
{
cnt[cur] += val;
sum[cur] = (long long)cnt[cur] * plc;
return;
}
shift(cur);
int mid = (s + e) / 2;
if (plc < mid) add(plc, val, cur * 2, s, mid);
else add(plc, val, cur * 2 + 1, mid, e);
merge(cur);
}

void del(int lo, int hi, int cur, int s, int e)
{
if (lo >= hi) return;
if (lo == s && hi == e)
{
cnt[cur] = sum[cur] = 0;
return;
}
shift(cur);
int mid = (s + e) / 2;
if (lo < mid) del(lo, min(hi, mid), cur * 2, s, mid);
if (hi > mid) del(max(lo, mid), hi, cur * 2 + 1, mid, e);
merge(cur);
}

plp find(int num, int cur, int s, int e)
{
if (e - s < 2)
return plp((long long)num * s, pii(s, -num));
shift(cur);
int mid = (s + e) / 2; plp ret;
if (cnt[cur * 2] >= num) ret = find(num, cur * 2, s, mid);
else ret = find(num - cnt[cur * 2], cur * 2 + 1, mid, e), ret.first += sum[cur * 2];
merge(cur);
return ret;
}

int main()
{
ios::sync_with_stdio(false);
ll t, c; string s;
while (cin >> s)
{
cin >> t >> c;
if (s[0] == 'A')
add(c, t, 1, 0, MAXN);
else
{
plp ans = find(t, 1, 0, MAXN);
if (ans.second.first >= MAXN - 1 || ans.first > c)
cout << "UNHAPPY" << endl;
else
{
cout << "HAPPY" << endl;
del(0, ans.second.first, 1, 0, MAXN);
add(ans.second.first, ans.second.second, 1, 0, MAXN);
}
}
}
return 0;
}

see sub-tree reply to that message


::Login
Forgot password?

::News
22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553).
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).

::Counter

Server time: 2017-11-23 04:34:50Online Contester Team © 2002 - 2016. All rights reserved.