oj.uz

답안 #774954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
774954 2023-07-06T06:15:27 Z tpd2k Addk (eJOI21_addk) C++14
92 / 100
 1248 ms 6168 KB 
// teddybear's code
// the one who loves NBP
// noe the second
// goal: 0 / 8
// get medal in APIO (like TKN)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

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

#define FOR(i,n) for (int i = 0; i<n; i++)
using ll = long long;
using ull = unsigned long long;
ll n,m,t;
ll cnt = 0;
const int maxn = 1e5;
const ll mod = 1e9 + 7;
#define Y "YES"
#define N "NO"

bool visited[1005][1005];
int dist[1005][1005];
int w,h;
int fx[4] = {-1, 1, 0, 0};
int fy[4] = {0, 0, -1, 1};
queue <pair<int,int>> q;

ll st[4 * maxn + 20];
ll a[maxn + 20];

void build(int id, int l, int r)
{
	if (l == r)
	{
		st[id] = a[l];
		return;
	}
	
	int m = (l + r) / 2;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	
	st[id] = st[id*2] + st[id*2+1];
}

void update(int id, int l, int r, int lq, int rq, ll val)
{
	if (l > rq || r < lq)
	{
		return;
	}
	if (l >= lq && r <= rq)
	{
		st[id] = val;
		return;
	}
	
	int m = (l + r) / 2;
	update(id*2,l,m,lq,rq,val);
	update(id*2+1,m+1,r,lq,rq,val);
	
	st[id] = st[id*2] + st[id*2+1];
	
}

ll get(int id, int l, int r, int lq, int rq)
{
	if (l > rq || r < lq)
	{
		return 0;
	}
	if (l >= lq && r <= rq)
	{
		return st[id];
	}
	int m = (l + r) / 2;
	return get(id*2,l,m,lq,rq) + get(id*2+1,m+1,r,lq,rq);
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i<=n; i++)
	{
		cin >> a[i];
	}
	build(1,1,n);
	cin >> t;
	while (t--)
	{
		int num;
		cin >> num;
		if (num == 1)
		{
			ll change[11];
			
			for (int i = 0; i<m; i++)
			{
				cin >> change[i];
			}
			if (m == 1)
			{
				continue;
			}
			ll z = change[0];
			for (int i = 0; i<m-1; i++)
			{
				a[change[i]] = a[change[i+1]];
				update(1,1,n,change[i],change[i],a[change[i]]);
			}
			a[change[m-1]] = a[z];
			update(1,1,n,change[m-1],change[m-1],a[change[m-1]]);
		}
		else
		{
			ll x,y,dis;
			cin >> x >> y >> dis;
			ll total = get(1,1,n,x,y);
			ll x1 = x, y1 = y;
			ll sum = 0;
			ll dem = 0;
			/*while (x1 <= y1 && y1 >= x + dis - 1 && dem < dis)
			{
				sum += total;
				total -= a[x1];
				total -= a[y1];
				y1--;
				x1++;
				dem++;
				//cout << "! " << sum << '\n';
			}*/
			for (int i = 0; i<dis; i++)
			{
				sum += total;
				total -= a[x1];
				total -= a[y1];
				y1--;
				x1++;
				if (x1 > y1 || y1 < x + dis - 1)
				{
					break;
				}
			}
			cout << sum << '\n';
		}
	}
}

/*
8 3
7 2 5 1 9 3 4 6
3
2 2 7 4
1 2 5 8
2 2 7 3

8 3
7 2 5 1 9 3 4 6
1
2 2 7 4


*/

void init()
{
 	int te = 1; //cin >> te;
 	while (te--)
 	{
 	 	  solve();
 	}
}

void preprocess()
{

}


int main()
{
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL);
    //cin.tie(0); cout.tie(0);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
 	init();
 	preprocess();
 	//solve();
 	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:123:7: warning: unused variable 'dem' [-Wunused-variable]
  123 |    ll dem = 0;
      |       ^~~

Subtask #1
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 352 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Correct 5 ms 536 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Correct 8 ms 724 KB Output is correct
8 Correct 11 ms 784 KB Output is correct
9 Correct 19 ms 972 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 1700 KB Output is correct
2 Correct 134 ms 2192 KB Output is correct
3 Correct 231 ms 3192 KB Output is correct
4 Correct 781 ms 5512 KB Output is correct
5 Correct 1248 ms 6168 KB Output is correct
6 Correct 1110 ms 5976 KB Output is correct
7 Correct 943 ms 6088 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 198 ms 2244 KB Output isn't correct
2 Halted 0 ms 0 KB -