oj.uz

답안 #572128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572128 2022-06-03T17:54:05 Z beaconmc 말 (IOI15_horses) C++14
54 / 100
 417 ms 88344 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
#define double long double
#define SIZE 1048576
#define HSIZE 524288
#define MOD 1000000007
// #include "horses.h"
using namespace std;

vector<ll> x, y, xx, yy;
ll n;


ll tree[SIZE];
ll tree2[SIZE];

set<vector<ll>> ranges;

void update(ll a,ll b){
    a += HSIZE;
    tree[a] = b;
    while (a>1){
        a/=2;
        tree[a] = tree[a*2]*tree[a*2+1]%MOD;
    }
}
void update2(ll a,ll b){
    a += HSIZE;
    tree2[a] = b;
    while (a>1){
        a/=2;
        tree2[a] = max(tree2[a*2], tree2[a*2+1]);
    }
}

ll query(ll a, ll b){
    a += HSIZE;
    b += HSIZE;
    ll maxi = 1;
    while (a<=b){
        if (a%2==1){
            maxi *= tree[a++]; 
            maxi %= MOD;
        }
        if (b%2==0){
            maxi *= tree[b--];
            maxi %= MOD;
        }
        a/=2; b/=2;
    }
    return maxi;
}
ll query2(ll a, ll b){
    a += HSIZE;
    b += HSIZE;
    ll maxi = 0;
    while (a<=b){
        if (a%2==1){
            maxi = max(maxi, tree2[a++]); 
        }
        if (b%2==0){
            maxi = max(maxi, tree2[b--]);
        }
        a/=2; b/=2;
    }
    return maxi;
}




int solve(){

	vector<ll> xx;
	vector<ll> yy;
	vector<ll> pos;

	ll cur = 30;
	auto it = ranges.end();

	while (cur--){
		it--;
		xx.push_back(x[(*it)[0]]);
		yy.push_back(query2((*it)[0], (*it)[1]));
		pos.push_back((*it)[0]);
		if (it==ranges.begin()){
			break;
		}
	}
	reverse(xx.begin(), xx.end());
	reverse(yy.begin(), yy.end());
	reverse(pos.begin(), pos.end());

	cur = 1;
	ll maxsum = 1;
	ll maxpos = -1;

	FOR(i,0, xx.size()){
		cur *= xx[i];
		if (yy[i] * cur >= maxsum){
			cur = 1;
			maxsum = yy[i];
			maxpos = i;
		}
	}



	return (query(0, pos[maxpos]) * maxsum) % 1000000007;
}

int init(int N, int X[], int Y[]) {
	n = N;
	FOR(i,0,N){
		x.push_back(X[i]);
		update(i, X[i]);
		y.push_back(Y[i]);
		update2(i, Y[i]);
	}
	ll prev = -1;

	FORNEG(i, n-1, -1){
		if (x[i] == 1 && prev==-1){
			prev = i;
		}

		if (x[i] != 1){
			if (prev != -1){
				ranges.insert({i, prev});
				prev = -1;
			}else{
				ranges.insert({i,i});
			}
		}
	}


	if (prev != -1){
		ranges.insert({0, prev});
	}


	return solve();

}

int updateX(int pos, int val) {
	if (x[pos] == val) return solve();
	update(pos, val);
	if (pos!=0){
		if (x[pos] == 1 && val != 1){
			auto it = ranges.upper_bound({pos, 999999999});
			it--;
			vector<ll> first = *it;
			ranges.insert({first[0], pos-1});
			ranges.insert({pos, first[1]});
			ranges.erase(it);
		}


		if (x[pos] != 1 && val == 1){
			auto it = ranges.upper_bound({pos, 999999999});
			it--;
			vector<ll> first = *it;
			it --;
			vector<ll> second = *it;
			ranges.erase(first);ranges.erase(second);
			ranges.insert({second[0], first[1]});
		}
	}


	x[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
	update2(pos, val);
	y[pos] = val;
	return solve();

}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:78:13: warning: declaration of 'xx' shadows a global declaration [-Wshadow]
   78 |  vector<ll> xx;
      |             ^~
horses.cpp:14:18: note: shadowed declaration is here
   14 | vector<ll> x, y, xx, yy;
      |                  ^~
horses.cpp:79:13: warning: declaration of 'yy' shadows a global declaration [-Wshadow]
   79 |  vector<ll> yy;
      |             ^~
horses.cpp:14:22: note: shadowed declaration is here
   14 | vector<ll> x, y, xx, yy;
      |                      ^~
horses.cpp:5:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  102 |  FOR(i,0, xx.size()){
      |      ~~~~~~~~~~~~~~              
horses.cpp:102:2: note: in expansion of macro 'FOR'
  102 |  FOR(i,0, xx.size()){
      |  ^~~
horses.cpp:113:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  113 |  return (query(0, pos[maxpos]) * maxsum) % 1000000007;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 3 ms 580 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 540 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 3 ms 596 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 448 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 357 ms 75632 KB Output is correct
2 Correct 400 ms 75664 KB Output is correct
3 Correct 386 ms 75640 KB Output is correct
4 Correct 381 ms 75608 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 3 ms 580 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 452 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 4 ms 596 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 123 ms 32020 KB Output is correct
34 Correct 123 ms 32048 KB Output is correct
35 Correct 300 ms 85596 KB Output is correct
36 Correct 316 ms 85668 KB Output is correct
37 Correct 116 ms 30116 KB Output is correct
38 Correct 187 ms 54764 KB Output is correct
39 Correct 106 ms 29912 KB Output is correct
40 Correct 314 ms 80684 KB Output is correct
41 Incorrect 110 ms 29988 KB Output isn't correct
42 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 4 ms 604 KB Output is correct
26 Correct 3 ms 596 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 1 ms 452 KB Output is correct
30 Correct 3 ms 600 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 382 ms 79572 KB Output is correct
34 Correct 417 ms 88344 KB Output is correct
35 Correct 407 ms 79388 KB Output is correct
36 Correct 390 ms 83300 KB Output is correct
37 Correct 123 ms 32052 KB Output is correct
38 Correct 126 ms 31992 KB Output is correct
39 Correct 303 ms 85620 KB Output is correct
40 Correct 315 ms 85588 KB Output is correct
41 Correct 119 ms 30136 KB Output is correct
42 Correct 197 ms 54816 KB Output is correct
43 Correct 104 ms 30024 KB Output is correct
44 Correct 320 ms 80728 KB Output is correct
45 Incorrect 104 ms 29988 KB Output isn't correct
46 Halted 0 ms 0 KB -