oj.uz

Submission #142792

# Submission time Handle Problem Language Result Execution time Memory
142792 2019-08-11T04:30:39 Z cheetose 역사적 조사 (JOI14_historical) C++11
100 / 100
 2389 ms 8172 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 1987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int n,m,sz,N;
ll a[100000];
int cnt[1000001];
ll ans[100000];
struct query {
	int l, r, i;
	query() :query(0, 0, 0) {}
	query(int L, int R, int I) :l(L), r(R), i(I) {}
	bool operator < (const query& Q)
	{
		int lg = r / sz, rg = Q.r / sz;
		return lg == rg ? l < Q.l : lg < rg;
	}
}q[100000];
Vll vv;

ll tree[200005];
inline void add(int x)
{
	tree[x+N]+=vv[x];
	for(int i=(x+N)/2;i>0;i>>=1)tree[i]=max(tree[i*2],tree[i*2+1]);
}
inline void erase(int x)
{
	tree[x+N]-=vv[x];
	for(int i=(x+N)/2;i>0;i>>=1)tree[i]=max(tree[i*2],tree[i*2+1]);
}
int main() {
	scanf("%d%d",&n,&m);
	sz = sqrt(n);
	fup(i, 0, n - 1, 1)
	{
		scanf("%lld", a + i);
		vv.pb(a[i]);
	}
	sort(ALL(vv));
	vv.resize(unique(ALL(vv))-vv.begin());
	fup(i,0,n-1,1)a[i]=lower_bound(ALL(vv),a[i])-vv.begin();
	N=vv.size();
	fup(i, 0, m - 1, 1)
	{
		int L, R;
		scanf("%d%d", &L, &R);
		q[i] = query(L-1, R-1, i);
	}
	sort(q, q + m);
	int L = 0, R = 0;
	add(a[0]);
	for (int i = 0; i < m; i++)
	{
		int nl = q[i].l, nr = q[i].r;
		if (nr > R)
		{
			for (int k = R + 1; k <= nr; k++)
				add(a[k]);
		}
		if (nr<R)
		{
			for (int k = R; k > nr; k--)
				erase(a[k]);
		}
		if (nl < L)
		{
			for (int k = L - 1; k >= nl; k--)
				add(a[k]);
		}
		if (nl > L)
		{
			for (int k = L; k < nl; k++)
				erase(a[k]);
		}
		ans[q[i].i] = tree[1];
		L = nl, R = nr;
	}
	fup(i, 0, m - 1, 1)printf("%lld\n", ans[i]);
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
historic.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
   ~~~~~^~~~~~~~~~~~~~~
historic.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &L, &R);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Correct 3 ms 1528 KB Output is correct
13 Correct 3 ms 1528 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct
15 Correct 3 ms 1528 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1528 KB Output is correct
3 Correct 4 ms 1528 KB Output is correct
4 Correct 6 ms 1656 KB Output is correct
5 Correct 10 ms 1656 KB Output is correct
6 Correct 16 ms 1784 KB Output is correct
7 Correct 15 ms 1784 KB Output is correct
8 Correct 14 ms 1784 KB Output is correct
9 Correct 15 ms 1784 KB Output is correct
10 Correct 20 ms 1912 KB Output is correct
11 Correct 21 ms 1912 KB Output is correct
12 Correct 21 ms 1824 KB Output is correct
13 Correct 22 ms 1912 KB Output is correct
14 Correct 19 ms 1912 KB Output is correct
15 Correct 19 ms 1784 KB Output is correct
16 Correct 14 ms 1784 KB Output is correct
17 Correct 12 ms 1912 KB Output is correct
18 Correct 19 ms 1784 KB Output is correct
19 Correct 20 ms 1912 KB Output is correct
20 Correct 21 ms 1912 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 4 ms 1532 KB Output is correct
5 Correct 4 ms 1656 KB Output is correct
6 Correct 4 ms 1656 KB Output is correct
7 Correct 6 ms 1784 KB Output is correct
8 Correct 9 ms 2040 KB Output is correct
9 Correct 15 ms 2420 KB Output is correct
10 Correct 13 ms 2744 KB Output is correct
11 Correct 81 ms 6120 KB Output is correct
12 Correct 36 ms 3952 KB Output is correct
13 Correct 57 ms 4844 KB Output is correct
14 Correct 89 ms 6252 KB Output is correct
15 Correct 123 ms 7960 KB Output is correct
16 Correct 83 ms 7276 KB Output is correct
17 Correct 39 ms 4204 KB Output is correct
18 Correct 71 ms 6248 KB Output is correct
19 Correct 73 ms 8172 KB Output is correct
20 Correct 43 ms 6124 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2168 KB Output is correct
2 Correct 113 ms 2684 KB Output is correct
3 Correct 257 ms 3188 KB Output is correct
4 Correct 464 ms 3952 KB Output is correct
5 Correct 673 ms 4436 KB Output is correct
6 Correct 700 ms 5100 KB Output is correct
7 Correct 639 ms 5612 KB Output is correct
8 Correct 502 ms 6316 KB Output is correct
9 Correct 421 ms 6868 KB Output is correct
10 Correct 322 ms 6860 KB Output is correct
11 Correct 656 ms 6888 KB Output is correct
12 Correct 1004 ms 7016 KB Output is correct
13 Correct 1487 ms 7272 KB Output is correct
14 Correct 2163 ms 7736 KB Output is correct
15 Correct 2373 ms 8168 KB Output is correct
16 Correct 2389 ms 7916 KB Output is correct
17 Correct 2304 ms 7788 KB Output is correct
18 Correct 2216 ms 7748 KB Output is correct
19 Correct 2176 ms 7696 KB Output is correct
20 Correct 2151 ms 7788 KB Output is correct
21 Correct 2177 ms 7604 KB Output is correct
22 Correct 2199 ms 7620 KB Output is correct
23 Correct 2173 ms 7784 KB Output is correct
24 Correct 2152 ms 7584 KB Output is correct
25 Correct 258 ms 7660 KB Output is correct