Triathlon

Triathlon - CodeChef

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)

#define all(x) (x).begin(), (x).end()
#define unq(x) (x.resize(unique(all(x)) - x.begin()))

#define inf LLONG_MAX
#define mxm  200005
#define mod 1000000007
#define pi acos(-1)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector< pll > vll;
typedef vector<string> vs;
typedef vector<ll> vL;
typedef unsigned long long ull;
typedef double D;
typedef long double LD;
//int dx[]= {0,0,-1,1,1,-1,1,-1};
//int dy[]= {-1,1,0,0,1,-1,-1,1};
ll n, x[mxm], y[mxm], z[mxm], id, sum = 0, mn = inf, mx = -1;
int main() {
    
    scanf("%lld", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld %lld %lld", &x[i], &y[i], &z[i]);
        sum += x[i];
        if (y[i] + z[i] < mn)
            mn = y[i] + z[i];
        if (y[i] + z[i] > mx){
            mx = y[i] + z[i];
            id = i;}
    }

    if (mx > sum-x[id] + mn)
        printf("%lld\n", mx+x[id]);
    else
        printf("%lld\n", sum+mn);
    return 0;
}

86D - Powerful array

problem

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)

#define modulo(S, N) ((S) & (N - 1)) // returns S % N, where N is a power of 2
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
#define turnOffLastBit(S) ((S) & (S - 1))
#define turnOnLastZero(S) ((S) | (S + 1))
#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))

#define all(x) (x).begin(), (x).end()
#define unq(x) (x.resize(unique(all(x)) - x.begin()))

#define inf LLONG_MAX
#define mx  200005
#define mod 1000000007
#define block 555
#define A 1111111

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector< pll > vll;
typedef vector<string> vs;
typedef unsigned long long ull;
typedef double D;
typedef long double LD;
//int dx[]= {0,0,-1,1,1,-1,1,-1};
//int dy[]= {-1,1,0,0,1,-1,-1,1};

ll cnt[A],a[mx],ans=0,answer[mx];


struct query
{
    int L,R,i;
} q[mx];

bool compare(query x, query y)
{
    if(x.L/block != y.L/block)
    {
        return x.L/block < y.L/block;
    }
    return x.R < y.R;
}

void remove(int i)
{
    cnt[a[i]]--;

    ans -= (2ll*cnt[a[i]]+1)*a[i];

}

void add(int i)
{
    cnt[a[i]]++;
    ans += (2ll*cnt[a[i]]-1)*a[i];
}

int main()
{
    ll n,m;
    scanf("%lld %lld",&n,&m);
    for(int i=0; i<n; i++)
        scanf("%lld",&a[i]);
//    scanf("%lld",&m);
    for(int i=0; i<m; i++)
    {
        scanf("%lld %lld",&q[i].L,&q[i].R);
        q[i].L--;
        q[i].R--;
        q[i].i = i;
    }

    sort(q,q+m,compare);

    int currentL=0,currentR=0;
    for(int j=0; j<m; j++)
    {
        int L = q[j].L, R = q[j].R;
        while(currentL < L)
        {
            remove(currentL);
            currentL++;
        }
        while(currentL > L)
        {
            add(currentL-1);
            currentL--;
        }
        while(currentR <= R)
        {
            add(currentR);
            currentR++;
        }
        while(currentR > R+1)
        {
            remove(currentR-1);
            currentR--;
        }
        answer[q[j].i] = ans;
    }

    for(int i=0; i<m; i++)
        printf("%lld\n",answer[i]);
    return 0;
}

DQUERY - D-query

DQUERY

MO’s Algorithm 

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)

#define modulo(S, N) ((S) & (N - 1)) // returns S % N, where N is a power of 2
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
#define turnOffLastBit(S) ((S) & (S - 1))
#define turnOnLastZero(S) ((S) | (S + 1))
#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))

#define all(x) (x).begin(), (x).end()
#define unq(x) (x.resize(unique(all(x)) - x.begin()))

#define inf LLONG_MAX
#define mx  200005
#define mod 1000000007
#define block 555
#define A 1111111

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector< pll > vll;
typedef vector<string> vs;
typedef unsigned long long ull;
typedef double D;
typedef long double LD;
//int dx[]= {0,0,-1,1,1,-1,1,-1};
//int dy[]= {-1,1,0,0,1,-1,-1,1};

int cnt[A],a[mx],ans=0,answer[mx];
struct query
{
    int L,R,i;
} q[mx];

bool compare(query x, query y)
{
    if(x.L/block != y.L/block)
    {
        return x.L/block < y.L/block;
    }
    return x.R < y.R;
}

void remove(int i)
{
    cnt[a[i]]--;
    if(cnt[a[i]]==0)
        ans--;
}

void add(int i)
{
    cnt[a[i]]++;
    if(cnt[a[i]]==1)
        ans++;
}

int main()
{
    ll n,m;
    scanf("%lld",&n);
    for(int i=0; i<n; i++)
        scanf("%lld",&a[i]);
    scanf("%lld",&m);
    for(int i=0; i<m; i++)
    {
        scanf("%lld %lld",&q[i].L,&q[i].R);
        q[i].L--;
        q[i].R--;
        q[i].i = i;
    }
    sort(q,q+m,compare);
    int currentL=0,currentR=0;
    for(int j=0; j<m; j++)
    {
        int L = q[j].L, R = q[j].R;
        while(currentL < L)
        {
            remove(currentL);
            currentL++;
        }
        while(currentL > L)
        {
            add(currentL-1);
            currentL--;
        }
        while(currentR <= R)
        {
            add(currentR);
            currentR++;
        }
        while(currentR > R+1)
        {
            remove(currentR-1);
            currentR--;
        }
        answer[q[j].i] = ans;
    }

    for(int i=0; i<m; i++)
        printf("%d\n",answer[i]);
    return 0;
}

1112 - Curious Robin Hood

#include<bits/stdc++.h>
using namespace std;
long long arry[100010],segment[400050];
 
void build(long long at, long long L, long long R)
{
    if(L==R)
    {
        segment[at] = arry[L];
        return;
    }
    long long mid = (L+R)/2;
    build(at*2,L,mid);
    build(at*2+1,mid+1,R);
    segment[at] = segment[at*2] + segment[at*2+1];
}
 
void update(long long at, long long L, long long R, long long pos, long long u)
{
    if(L==R)
    {
        segment[at] += u;
        return;
    }
    long long mid = (L+R)/2;
    if(pos <= mid)
        update(at*2,L,mid,pos,u);
    else
        update(at*2+1,mid+1,R,pos,u);
    segment[at] = segment[at*2]+segment[at*2+1];
}
 
long long query(long long at,long long L, long long R, long long l, long long r)
{
    if(r<L || l>R)
        return 0;
    if(L==R)
        return segment[at];
    if(l <= L && r >= R)
        return segment[at];
    long long mid = (L+R)/2;
    long long x = query(at*2, L, mid, l, r);
    long long y = query(at*2+1, mid+1, R, l, r);
    return x + y;
}
 
int main()
{
    //freopen("T - Curious Robin Hood.txt","r",stdin);
    long long T,n,q,a,b,i,c=1;
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld %lld", &n, &q);
        for(i=1; i<=n; i++)
            scanf("%lld", &arry[i]);
 
        build(1,1,n);
        printf("Case %lld:\n",c++);
        for(i=1; i<=q; i++)
        {
            scanf("%lld",&a);
            if(a==1)
            {
                scanf("%lld",&b);
                update(1,1,n,b+1,-arry[b+1]);
                printf("%lld\n",arry[b+1]);
                arry[b+1] = 0;
            }
            else if(a==2)
            {
                scanf("%lld %lld",&a,&b);
                update(1,1,n,a+1,b);
                arry[a+1] += b;
            }
            else
            {
                scanf("%lld %lld", &a, &b);
                printf("%lld\n",query(1,1,n,a+1,b+1));
            }
        }
    }
    return 0;
}