So, i accidentally wrote a suboptimal solution for this problem (stored entire sequences of settings instead of just singular changes from the previous ones), saw it taking 15s (about 8 without the output) to complete max test on my laptop but submitted for fun anyway. Got AC in 0.4s. Go figure.

 sigma (((a*x+b)/c)^k)    l<=x<=r     1<=a,b,c<=10^9    1<=k<=50

how to solve??

http://www.lydsy.com/JudgeOnline/problem.php?id=3913

#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>

using namespace std;
int a,b,c,d;
int main()
{
    cin >> a >> b >> c >> d;
    int h = c;
    if(a >= c)
    {
        cout << a;
        return 0;
    }
    while(1)
    {
        if(a == c)
        {
            cout << a;
            return 0;
        }
        a+=b;
        if(c-d >= a) c-=d; else
        {
            if(a > h) cout << h; else
            cout << a;
            return 0;
        }
    }
    return 0;
}

Subj

For the max test (a hundred 100's) the answer is 7955128.99. For ninety nine 1m sides and one 98m side it's 397.86.
Use this to check your precision.

infin = 100000000 - wa14.
infin = 1000000 - ac.

6
0 3
0 0
3 0
0 3
1 2
2 1

answer 5 (0 0 is not)

16
15 15
16 17
17 19
18 21
19 23
75 19
16 62
13 69
10 76
7 83
4 90
1 97
-2 104
-5 111
-8 118
-11 125

answer: 10 (last 10)

13
1 1
1 1
1 1
16 62
13 69
10 76
7 83
4 90
1 97
-2 104
-5 111
-8 118
-11 125

answer: 10 (last 10 your program could get 10 in prev test and get 13 here)


8
1 1
1 1
1 1
0 0
0 0
0 0
0 0
2 2

answer 8

5
4 4
4 4
4 4
4 4
4 4

answer 5

I hope, it will help you (P.S. you can click on my nickname and write me, i with big pleasure help you)

Edited by author 03.03.2017 22:18

I resolved WA21 using this case:

1 5
1 1 2 3 4

Correct Answer => 1

the problem with my solution was initialisation of the slope in case the first 2 elements are equal.

using binary search r, and check for each segment,find the inner side part of other segment
that distance is smaller than 2*r,get the segment of these points in each line, check if union of them is the hole line segment.

for check two segments' distance we only need to check innerside adjctent two line segments

it can be done by O(n*log(n)) sweepline precalculate..

i wrote code using int (not long) and got AC. Add more tests!

I have tried with a greedy algorithm but gives WA#8, any tests pls?

Why "wrong answer"?
a=input()
if 0<a<5:
    print('few')
elif 4<a<10:
    print("sveral")
elif 9<a<20:
    print("pack")
elif 19<a<50:
    print("lots")
elif 49<a<100:
    print('horde')
elif 99<a<250:
    print('throng')
elif 249<a<500:
    print("swarm")
elif 499<a<1000:
    print("zounds")
elif 1000<a:
    print ('legion')

In c++ use scanf, or write this:
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

And in main func write sync;

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int MIN = 1, MAX = 8;

int free(int x0, int y0) {
    int c = 0; double r0 = sqrt(5), r;
    for (int x = x0 - 2; x <= x0 + 2; x++)
        for (int y = y0 - 2; y <= y0+2; y++) {
            r = sqrt(pow(x - x0, 2) + pow(y - y0, 2));
            if (r == r0 && x >= MIN && x <= MAX && y >= MIN && y <= MAX) c++;
        }

    return c;
}

int main() {
    int T; // kolichestvo testovyx blokov
    cin >> T; cin.ignore();

    int x, y;
    for (int t = 0; t < T; t++) {
        x = cin.get() - 'a' + 1;
        y = cin.get() - '0';
        cout << free(x, y) << endl;
        cin.ignore();
    }
}

Edited by author 20.11.2016 00:44

How did the sample output was calculated to be 2?
1st page will have 3 lines :

To be
or
not

2nd page will have only one line:

to be

Is my understanding correct?

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define ppb pop_back
#define mp make_pair

#define pii pair <int, int>
#define pll pair <ll, ll>
#define ld long double
#define ll long long
#define ull unsigned ll

#define bit(x) __builtin_popcountll(x)
#define all(x) x.begin(), x.end()
#define sqr(x) ((x) * 1ll * (x))
#define sz(x) (int)x.size()

#define purple ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rep(_i, _from, _to) for (int _i = _from; _i <= _to; _i++)
#define per(_i, _from, _to) for (int _i = _from; _i >= _to; _i--)

#define nl '\n'
#define ioi exit(0);

#define _225day ""

using namespace std;

const int N = 1e6 + 7, mod = 1e9 + 9, inf = 1e9 + 7;
const ll linf = (ll)1e18 + 7;
const ld eps = 1e-15, pi = 3.141592;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};


  int n, m, base = 50000;
  int s[N];
  pii a[N];

  struct Tree{
    int ans, add;
  } t[N << 2];


  inline bool cmp(pii x, pii y){
    if (x.f != y.f) return x.f < y.f;
  }

  inline bool Check(int pref){
    memset(s, 0, sizeof(s));
    rep(i, 1, pref)
      s[a[i].f]++, s[a[i].s + 1]--;

    rep(i, 0, m + base){
      s[i] += s[i - 1];
      if (i > base && !s[i]) return 0;
    }

    return 1;
  }

  inline void Push(int v, int tl, int tr){
    if (t[v].add && tl != tr){
      t[v + v].add += t[v].add, t[v + v + 1].add += t[v].add;
      t[v + v].ans += t[v].add, t[v + v + 1].ans += t[v].add;
      t[v].add = 0;
    }
  }

  inline void Update(int l, int r, int add, int v = 1, int tl = 0, int tr = N){
    Push(v, tl, tr);
    if (l <= tl && tr <= r){
      t[v].ans += add;
      t[v].add += add;
      return;
    }
    if (tl > r || tr < l) return;
    int tm = tl + tr >> 1;
    Update(l, r, add, v + v, tl, tm);
    Update(l, r, add, v + v + 1, tm + 1, tr);
    t[v].ans = min(t[v + v].ans, t[v + v + 1].ans);
  }

  inline int Get(int l, int r, int v = 1, int tl = 0, int tr = N){
    Push(v, tl, tr);
    if (l <= tl && tr <= r) return t[v].ans;
    if (tl > r || tr < l) return inf;
    int tm = tl + tr >> 1;
    return min(Get(l, r, v + v, tl, tm), Get(l, r, v + v + 1, tm + 1, tr));
  }

int main(){
  #ifndef _225day
    freopen (_225day".in", "r", stdin);
    freopen (_225day".out", "w", stdout);
  #endif

  cin >> m;
  while (1){
    int x, y;
    cin >> x >> y;
    if (x == 0 && y == 0) break;
    a[++n] = {x + base + 1, y + base};
  }

  sort (a + 1, a + 1 + n, cmp);
  int l = 1, r = n, ans = -1, mid;
  while (l <= r){
    mid = l + r >> 1;
    if (Check(mid)) ans = mid, r = mid - 1;
    else l = mid + 1;
  }

  if (ans == -1) cout << "No solution", ioi

  ans = n;
  rep(i, 1, ans)
    Update(a[i].f, a[i].s, 1);

  vector <pii> res;
  rep(i, 1, ans){
    Update(a[i].f, a[i].s, -1);
    if (!Get(base + 1, m + base))
      Update(a[i].f, a[i].s, 1), res.pb({a[i].f, a[i].s});
  }

  sort (all(res), cmp);
  cout << sz(res) << nl;
  for (auto i : res)
    cout << i.f - base - 1 << ' ' << i.s - base << nl;

  ioi
}

Can anybody give me some hint about test 14?

46 1836311903 -46 -1836311903 45

Is it because O(nm log (n + m)) solutions are not supposed to pass or something like that?
My solution has relatively high constant, but O(nm(n + m)) or O(nm log^2 (n + m)) solutions probably won't pass even if TL was bigger, I think.

Edited by author 29.03.2015 20:20