Submission #427985

#	Time	Username	Problem	Language	Result	Execution time	Memory
427985		Dan4Life	Horses (IOI15_horses)	C++17	0 / 100	19 ms	14488 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ll long long
#define fir first
#define sec second
const int MM = 1e9+7;
pair< pair<ll,ll>, ll> segtree[200000];
int nn, Y[500010];

pair<pair<ll,ll>,ll> combine(pair<pair<ll,ll>,ll> a, pair<pair<ll,ll>,ll> b)
{
    pair<pair<ll,ll>,ll> x;
    x.fir.fir = (a.fir.fir%MM)*(b.fir.fir%MM), x.fir.fir%=MM;
    if(a.fir.sec>b.fir.sec) x.fir.fir = a.fir.fir%MM, x.fir.sec = (x.fir.fir%MM)*(a.fir.sec%MM), x.fir.sec%=MM, x.sec = a.sec;
    else x.fir.sec = (x.fir.fir%MM)*(b.fir.sec%MM), x.fir.sec%=MM, x.sec = b.sec;
    return x;
}

void build(int p, int l, int r, int x[], int y[])
{
	if(l==r) segtree[p] = mp(mp(x[l],y[l]), l);
	else{
        int mid = (l+r)/2;
        build(p*2, l, mid, x, y);
        build(p*2+1, mid+1, r, x, y);
        segtree[p] = combine(segtree[p*2], segtree[p*2+1]);
	}
}

void update(int p, int l, int r, int pos, ll val, bool x)
{
    if(l==r){
        if(x) segtree[p].fir.fir = val;
        else segtree[p].fir.sec = val;
        return;
    }
    int mid = (l+r)/2;
    if(pos<=mid) update(p*2, l, mid, pos, val, x);
    else update(p*2+1, mid+1, r, pos, val, x);
    segtree[p] = combine(segtree[p*2], segtree[p*2+1]);
}

int query(int p, int L, int R, int l, int r)
{
    if(l>r)return 1ll;
    if(L>=l and R<=r) return segtree[p].fir.fir;
    int mid = (L+R)/2;
    int left = query(p*2, L, mid, l, min(r,mid));
    int right = query(p*2+1, mid+1, R, max(mid+1, l), r);
    int ans = (left%MM)*(right%MM);
    return ans%MM;
}

int init(int n, int x[], int y[])
{
    nn = n;
    for(int i = 0; i < n; i++) Y[i] = y[i];
	build(1, 0, n-1, x, y);
	int ind = segtree[1].sec;
	/*for(int i = 1; i < 4*nn; i++)
        cout << segtree[i].fir.fir << " " << segtree[i].fir.sec << " " << segtree[i].sec << "\n";
    cout << ind << "\n\n";*/
    return query(1, 0, n-1, 0, ind)*Y[ind];
}

int updateX(int pos, int val)
{
    update(1, 0, nn-1, pos, (ll)val, true);
    int ind = segtree[1].sec;
    /*for(int i = 1; i < 4*nn; i++)
        cout << segtree[i].fir.fir << " " << segtree[i].fir.sec << " " << segtree[i].sec << "\n";
    cout << ind << "\n\n";*/
    return query(1, 0, nn-1, 0, ind)*Y[ind];
}

int updateY(int pos, int val)
{
    Y[pos] = val;
    update(1, 0, nn-1, pos, val, false);
    int ind = segtree[1].sec;
    /*for(int i = 1; i < 4*nn; i++)
        cout << segtree[i].fir.fir << " " << segtree[i].fir.sec << " " << segtree[i].sec << "\n";
    cout << ind << "\n\n";*/
    return query(1, 0, nn-1, 0, ind)*Y[ind];
}

Compilation message (stderr)

horses.cpp: In function 'int query(int, int, int, int, int)':
horses.cpp:6:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    6 | #define fir first
      |             ^
horses.cpp:48:45: note: in expansion of macro 'fir'
   48 |     if(L>=l and R<=r) return segtree[p].fir.fir;
      |                                             ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:7:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    7 | #define sec second
      |             ^
horses.cpp:61:23: note: in expansion of macro 'sec'
   61 |  int ind = segtree[1].sec;
      |                       ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:7:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    7 | #define sec second
      |             ^
horses.cpp:71:26: note: in expansion of macro 'sec'
   71 |     int ind = segtree[1].sec;
      |                          ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:7:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    7 | #define sec second
      |             ^
horses.cpp:82:26: note: in expansion of macro 'sec'
   82 |     int ind = segtree[1].sec;
      |                          ^~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23