Cheating, of course :)

Любой массив можно отсортировать не более, чем за $$$\frac{n(n-1)}2$$$ операций. Подумайте либо угадайте, в каком случае понадобится ровно $$$\frac{n(n-1)}2$$$.

#include<iostream>

using namespace std;

int a[1000000+5];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        bool can=false;
        for (int i=1; i<n; i++)
        {
            if (a[i]>=a[i-1])
            {
                can=true;
                break;
            }
        }
        if (can) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}

Придумайте простой критерий, когда a_i & a_j >= a_i ^ a_j, рассмотрев биты от старшего к младшему. Примените его, чтобы быстро вычислить ответ.

#include<iostream>
#include<vector>
#include<algorithm>
#include<ctime>
#include<random>

using namespace std;

mt19937 rnd(time(NULL));

int a[1000000+5];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        int64_t ans=0;
        for (int j=29; j>=0; j--)
        {
            int64_t cnt=0;
            for (int i=0; i<n; i++)
            {
                if (a[i]>=(1<<j)&&a[i]<(1<<(j+1)))
                {
                    cnt++;
                }
            }
            ans+=cnt*(cnt-1)/2;
        }
        cout<<ans<<'\n';
    }
}

Используйте динамическое программирование.

#include <iostream>
#include <vector>

using namespace std;

inline int64_t calc(const vector<int> &a) {
	int n = a.size();
	vector<int64_t> d1(n+1), d2(n+1);
	d1[0] = -static_cast<int64_t>(1e18);
	d2[0] = 0;
	for (int i = 0; i < n; ++i) {
		d1[i+1] = max(d1[i], d2[i] + a[i]);
		d2[i+1] = max(d2[i], d1[i] - a[i]);
	}
	return max(d1.back(), d2.back());
}

int main() {
	ios_base::sync_with_stdio(false);
	int t; cin >> t;
	while (t--) {
		int n, q; cin >> n >> q;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		cout << calc(a) << "\n";
		for (int i = 0; i < q; ++i) {
			int l, r; cin >> l >> r; --l; --r;
			swap(a[l], a[r]);
			cout << calc(a) << "\n";
		}
	}
	return 0;
}

Здесь динамическое программирование не сработает. Подумайте, выгодно ли брать в ответ что-либо, кроме локальных минимумов и максимумов.

import java.io.*;
import java.util.*;

public class C2_Java {
    int[] a;
    int n;
    long ans;
    
    void add(int i, int sign) {
        if (i == 0 || i == n+1) return;
        if (a[i-1] < a[i] && a[i] > a[i+1]) ans += sign * a[i];
        if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= sign * a[i];
    }
    
    void addTwo(int l, int r, int sign) {
        if (l == r) return;
        if (l+1 == r) {
            add(l-1, sign);
            add(l, sign);
            add(r, sign);
            add(r+1, sign);
            return;
        }
        add(l-1, sign);
        add(l, sign);
        add(l+1, sign);
        if (l+2 != r) add(r-1, sign);
        add(r, sign);
        add(r+1, sign);
    }
    
    public void run() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer tok = new StringTokenizer(in.readLine());
        int t = Integer.parseInt(tok.nextToken());
        while (t --> 0) {
            tok = new StringTokenizer(in.readLine());
            n = Integer.parseInt(tok.nextToken());
            int q = Integer.parseInt(tok.nextToken());
            a = new int[n + 2];
            tok = new StringTokenizer(in.readLine());
            for (int i = 1; i <= n; ++i) {
                a[i] = Integer.parseInt(tok.nextToken());
            }
            a[0] = -1;
            a[n+1] = -1;
            ans = 0;
            StringBuilder builder = new StringBuilder();
            for (int i = 1; i <= n; ++i) {
                if (a[i-1] < a[i] && a[i] > a[i+1]) ans += a[i];
                if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= a[i];
            }
            builder.append(ans).append("\n");
            while (q --> 0) {
                tok = new StringTokenizer(in.readLine());
                int l = Integer.parseInt(tok.nextToken());
                int r = Integer.parseInt(tok.nextToken());
                if (l == r) {
                    builder.append(ans).append("\n");
                    continue;
                }
                addTwo(l, r, -1);
                int tmp = a[l];
                a[l] = a[r];
                a[r] = tmp;
                addTwo(l, r, +1);
                builder.append(ans).append("\n");
            }
            out.write(builder.toString());   
        }
        
        in.close();
        out.close();        
    }

    public static void main(String[] args) throws IOException {
        (new C2_Java()).run();
    }
}

#include<iostream>

using namespace std;

#define int long long

int a[1000000+5];

int n;

int ans=0;

inline void insert(int i)
{
    if (i==0||i==n+1) return;
    if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];
    if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];
}

inline void erase(int i)
{
    if (i==0||i==n+1) return;
    if (a[i-1]<a[i]&&a[i]>a[i+1]) ans-=a[i];
    if (a[i-1]>a[i]&&a[i]<a[i+1]) ans+=a[i];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int q;
        cin>>n>>q;
        for (int i=1; i<=n; i++)
        {
            cin>>a[i];
        }
        a[0]=-1;
        a[n+1]=-1;
        ans=0;
        for (int i=1; i<=n; i++)
        {
            if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];
            if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];
        }
        cout<<ans<<'\n';
        while (q--)
        {
            int l,r;
            cin>>l>>r;
            erase(l-1);
            erase(l);
            erase(l+1);
            if (l!=r)
            {
                if (r-1!=l+1&&r-1!=l) erase(r-1);
                if (r!=l+1) erase(r);
                erase(r+1);
            }
            swap(a[l],a[r]);
            insert(l-1);
            insert(l);
            insert(l+1);
            if (l!=r)
            {
                if (r-1!=l+1&&r-1!=l) insert(r-1);
                if (r!=l+1) insert(r);
                insert(r+1);
            }
            cout<<ans<<'\n';
        }
    }
}

Пересечение любых $$$k$$$ отрезков либо пусто, либо дает отрезок. Зафиксируйте левую границу пересечения и посчитайте количество наборов из $$$k$$$ отрезков, у которых пересечение начинается в этой левой границе.

import java.io.*;
import java.util.*;

public class D_Java {
	public static final int MOD = 998244353;
	
	public static int mul(int a, int b) {
		return (int)((long)a * (long)b % MOD);
	}
	
	int[] f;
	int[] rf;
	
	public int C(int n, int k) {
		return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));
	}
	
	public static int pow(int a, int n) {
		int res = 1;
		while (n != 0) {
			if ((n & 1) == 1) {
				res = mul(res, a);
			}
			a = mul(a, a);
			n >>= 1;
		}
		return res;
	}
	
	static void shuffleArray(int[] a) {
		Random rnd = new Random();
		for (int i = a.length-1; i > 0; i--) {
			int index = rnd.nextInt(i + 1);
			int tmp = a[index];
			a[index] = a[i];
			a[i] = tmp;
		}
	}
	
	public static int inv(int a) {
		return pow(a, MOD-2);
	}
	
	public void doIt() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tok = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(tok.nextToken());
		int k = Integer.parseInt(tok.nextToken());
		
		f = new int[n+42];
		rf = new int[n+42];
		f[0] = rf[0] = 1;
		for (int i = 1; i < f.length; ++i) {
			f[i] = mul(f[i-1], i);
			rf[i] = mul(rf[i-1], inv(i));
		}
		
		int[] events = new int[2*n];
		for (int i = 0; i < n; ++i) {
			tok = new StringTokenizer(in.readLine());
			int le = Integer.parseInt(tok.nextToken());
			int ri = Integer.parseInt(tok.nextToken());
			events[i] = le*2;
			events[i + n] = ri*2 + 1;
		}
		shuffleArray(events);
		Arrays.sort(events);
		
		int ans = 0;
		int balance = 0;
		for (int r = 0; r < 2*n;) {
			int l = r;
			while (r < 2*n && events[l] == events[r]) {
				++r;
			}
			int added = r - l;
			if (events[l] % 2 == 0) {
				// Open event
				ans += C(balance + added, k);
				if (ans >= MOD) ans -= MOD;
				ans += MOD - C(balance, k);
				if (ans >= MOD) ans -= MOD;
				balance += added;
			} else {
				// Close event
				balance -= added;
			}
		}
		
		in.close();
		System.out.println(ans);
	}
	
	public static void main(String[] args) throws IOException {
		(new D_Java()).doIt();
	}
}

Давайте вместо массива из нулей и единиц будем хранить количество нулей между каждой парой соседних единиц. Как тогда будут выглядеть операции обмена? А как посчитать защищенность армии в таком случае?

Пусть нам дан исходный массив и конечный. Подумайте, за сколько операций можно первый превратить во второй.

Соедините все вместе и напишите ДП.

#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

template<typename T>
inline void umin(T &a, const T &b) {
	a = min(a, b);
}

template<typename T>
inline void umax(T &a, const T &b) {
	a = max(a, b);
}

int main() {
	ios_base::sync_with_stdio(false);
	
	int n; cin >> n;
	vector<int> a(n);
	for (int &x : a) {
		cin >> x;
	}
	a.push_back(1);
	
	vector<int> gg;
	for (int i = 0; i <= n; ++i) {
		int s = i;
		while (a[i] == 0) ++i;
		gg.push_back(i - s);
	}
	
	vector<int> p = gg;
	partial_sum(begin(p), end(p), begin(p));
	
	constexpr int mx = 103;
	constexpr int dx = mx + 1, dy = mx + 1, dz = mx * (mx + 1) / 2 + 1;
	static int dp[dx][dy][dz] = {};
	
	for (int i = 0; i < dx; ++i) {
		for (int j = 0; j < dy; ++j) {
			for (int k = 0; k < dz; ++k) {
				dp[i][j][k] = INT_MAX;
			}
		}
	}
	dp[0][0][0] = 0;
	
	int k = gg.size(), l = p.back();
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j <= l; ++j) {
			for (int s = 0; s <= n * (n-1) / 2; ++s) {
				if (dp[i][j][s] == INT_MAX) continue;
				for (int q = j; q <= l; ++q) {
					umin(dp[i+1][q][s + abs(q - p[i])], dp[i][j][s] + (q-j)*(q-j));
				}
			}
		}
	}
	
	int mn = INT_MAX;
	for (int s = 0; s <= n * (n-1) / 2; ++s) {
		umin(mn, dp[k][l][s]);
		int val = l*l - mn;
		assert(val % 2 == 0);
		cout << val/2 << " ";
	}
	cout << endl;
	
	return 0;
}

program sum;

{$Mode Delphi}

uses
  gmp;

var
  sa, sb: string;
  a, b: MPInteger;
begin
  readLn(sa);
  readLn(sb);
  a := sa; b := sb;
  writeLn(string(a + b));
end.

program F;

{$mode objfpc}{$h+}
{$optimization LEVEL3}

uses gmp;

var
  num: string;
  mpNum: MPInteger;
  root, rem: MPInteger;
begin
  readLn(num);
  mpNum := num;
  mpNum := mpNum - 1;
  z_sqrtrem(root, rem, mpNum);
  if rem < root then begin
    writeln(string(rem + 1));
  end else begin
    writeln(string(2 * root + 1 - rem));
  end;
end.

404 Not Found

#include <iostream>
#include <map>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	map<string, int> vals;
	vals["Tetrahedron"]  = 4;
	vals["Cube"]         = 6;
	vals["Octahedron"]   = 8;
	vals["Dodecahedron"] = 12;
	vals["Icosahedron"]  = 20;
	int n; cin >> n;
	int res = 0;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		res += vals[s];
	}
	cout << res << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class PolyhedronSums {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		HashMap<String, Integer> vals = new HashMap<String, Integer>();
		vals.put("Tetrahedron", 4);
		vals.put("Cube", 6);
		vals.put("Octahedron", 8);
		vals.put("Dodecahedron", 12);
		vals.put("Icosahedron", 20);
		int n = Integer.parseInt(reader.readLine());
		int res = 0;
		for (int i = 0; i < n; i++) {
			res += vals.get(reader.readLine());
		}	
		writer.write(Integer.toString(res));
		reader.close();
		writer.close();
	}
}

vals = {
	'Tetrahedron': 4,
	'Cube': 6,
	'Octahedron': 8,
	'Dodecahedron': 12,
	'Icosahedron': 20
}

n = int(input())
ans = 0
for i in range(0, n):
	ans += vals[input()]
print(ans)

Подумайте, какие отрезки выгодно брать, если Антон сначала занимается шахматами, потом программированием, и наоборот.

#include <iostream>
#include <algorithm>

const int infinity = 1234567890;

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int n; cin >> n;
	vector<pair<int, int> > a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	int m; cin >> m;
	vector<pair<int, int> > b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i].first >> b[i].second;
	}
	int minR1 = infinity, maxL1 = -infinity;
	int minR2 = infinity, maxL2 = -infinity;
	for (int i = 0; i < n; i++) {
		maxL1 = max(maxL1, a[i].first);
		minR1 = min(minR1, a[i].second);	
	}
	for (int i = 0; i < m; i++) {
		maxL2 = max(maxL2, b[i].first);
		minR2 = min(minR2, b[i].second);	
	}
	int res = max(maxL2 - minR1, maxL1 - minR2);
	cout << max(res, 0) << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class TwoSegments {
	public static final int infinity = 1234567890;
	
	public static class Segment {
		public int l;
		public int r;

		public Segment(int aL, int aR) {
			l = aL;
			r = aR;
		} 
	}
	
	private static Segment[] readList(BufferedReader reader) throws Exception {
		int n = Integer.parseInt(reader.readLine());
		Segment[] res = new Segment[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());		
			int l = Integer.parseInt(tokenizer.nextToken());
			int r = Integer.parseInt(tokenizer.nextToken());
			res[i] = new Segment(l, r);
		}
		return res;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		Segment[] a = readList(reader);
		Segment[] b = readList(reader);
		int minR1 = infinity, maxL1 = -infinity;
		int minR2 = infinity, maxL2 = -infinity;
		for (int i = 0; i < a.length; i++) {
			maxL1 = Math.max(maxL1, a[i].l);
			minR1 = Math.min(minR1, a[i].r);	
		}
		for (int i = 0; i < b.length; i++) {
			maxL2 = Math.max(maxL2, b[i].l);
			minR2 = Math.min(minR2, b[i].r);	
		}
		int res = Math.max(maxL2 - minR1, maxL1 - minR2);
		writer.write(Integer.toString(Math.max(res, 0)));
		reader.close();
		writer.close();
	}
}

infinity = 1234567890
minR1 = minR2 = infinity
maxL1 = maxL2 = -infinity
n = int(input())
for i in range(0, n):
	(l, r) = map(int, input().split())
	maxL1 = max(maxL1, l)
	minR1 = min(minR1, r)
m = int(input())
for i in range(0, m):
	(l, r) = map(int, input().split())
	maxL2 = max(maxL2, l)
	minR2 = min(minR2, r)
res = max(maxL2 - minR1, maxL1 - minR2);
print(max(res, 0))

Промоделируйте процесс, чтобы узнать, как изменялось количество зерна в амбаре.

#include <iostream>
#include <cstdint>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int64_t n, m;
	cin >> n >> m;
	if (n <= m) {
		cout << n << endl;
	} else {
		n -= m;
		int64_t l = 0, r = 2e9;
		while (l < r) {
			int64_t m = (l + r) / 2;
			int64_t val = m * (m+1) / 2;
			if (val >= n) {
				r = m;
			} else {
				l = m+1;
			}
		}
		cout << l + m << endl;
	}
	return 0;
}

import java.io.*;
import java.util.*;

public class SparrowsJava {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		long n = Long.parseLong(tokenizer.nextToken());
		long m = Long.parseLong(tokenizer.nextToken());	
		if (n <= m) {
			writer.write(Long.toString(n));
		} else {
			n -= m;
			long l = 0, r = (long)2e9;
			while (l < r) {
				long med = (l + r) / 2;
				long val = med * (med+1) / 2;
				if (val >= n) {
					r = med;
				} else {
					l = med+1;
				}
			}
			writer.write(Long.toString(l + m));
		}
		reader.close();
		writer.close();
	}
}

(n, m) = map(int, input().split())
if n <= m:
	print(n)
else:
	aM = m
	n -= m
	(l, r) = (0, int(2e9))
	while l < r:
		m = (l + r) // 2;
		val = m * (m+1) // 2;
		if val >= n:
			r = m
		else:
			l = m+1
	print(l + aM)

Решите упрощенную версию задачи. Пусть в нашей последлвательности сначала идет x открывающих скобок, потом y закрывающих скобок, притом последнюю открывающую скобку обязательно включать в ППСП. Используйте наивное решение, чтобы посмотреть, как будет выглядеть ответ. Подумайте, как действовать дальше.

#include <iostream>
#include <vector>
#include <cstdint>

using namespace std;

int mod = (int)1e9 + 7;

int64_t extGcd(int64_t a, int64_t b, int64_t& x, int64_t& y) { 
	if (!a) {
		x = 0;
		y = 1;
		return b;
	}
	int64_t x1, y1;
	int64_t d = extGcd(b % a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

inline int addMod(int a, int b, int m = mod) {
	return ((int64_t)a + b) % m;
}

inline int mulMod(int a, int b, int m = mod) {
	return ((int64_t)a * b) % m;
}

inline int divMod(int a, int b, int m = mod) {
	int64_t x, y;
	int64_t g = extGcd(b, m, x, y);
	if (g != 1) {
		cerr << "Bad gcd!" << endl;
		for (;;);
	}
	x = (x % m + m) % m;
	return mulMod(a, x, m);
}

const int factRange = 1000000;
int fact[factRange];

inline void precalcFactorials() {
	fact[0] = 1;
	for (int i = 1; i < factRange; i++) {
		fact[i] = mulMod(fact[i-1], i);
	}
}

inline int F(int n) {
	return (n < 0) ? 0 : fact[n];
}

inline int C(int k, int n) {
	return divMod(F(n), mulMod(F(n-k), F(k)));
}

int main() {
	ios_base::sync_with_stdio(false);
	string s; 
	cin >> s;
	int len = s.size();
	precalcFactorials();
	vector<int> opnLeft(len), clsRight(len);
	opnLeft[0] = (s[0] == '(') ? 1 : 0;
	for (int i = 1; i < len; i++) {
		opnLeft[i] = opnLeft[i-1] + ((s[i] == '(') ? 1 : 0);
	}
	clsRight[len-1] = (s[len-1] == ')') ? 1 : 0;
	for (int i = len-2; i >= 0; i--) {
		clsRight[i] = clsRight[i+1] + ((s[i] == ')') ? 1 : 0);
	}
	int res = 0;
	for (int i = 0; i < len; i++) {
		if (s[i] != '(' || clsRight[i] == 0) {
			continue;
		}
		int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
		res = addMod(res, add);
	}
	cout << res << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class BracketsJava {
	public static int mod = (int)1e9 + 7;
	
	public static class ExtGcdResult {
		long x;
		long y;
	}
	
	public static long extGcd(long a, long b, ExtGcdResult res) { 
		if (a == 0) {
			res.x = 0L;
			res.y = 1L;
			return b;
		}
		ExtGcdResult newRes = new ExtGcdResult();
		long d = extGcd(b % a, a, newRes); 
		res.x = newRes.y - (b / a) * newRes.x;
		res.y = newRes.x;
		return d; 
	}
	
	public static final int addMod(int a, int b) { 
		return (int)(((long)a + b) % mod); 
	}

	public static final int mulMod(int a, int b) { 
		return (int)(((long)a * b) % mod); 
	}
	
	public static final int divMod(int a, int b) { 
		ExtGcdResult res = new ExtGcdResult();
		long g = extGcd(b, mod, res); 
		if (g != 1) {
			System.out.println("Bad gcd!");
			for (;;);
		}
		int q = (int)((res.x % mod + mod) % mod); 
		return mulMod(a, q); 
	}
	
	public static final int[] precalcFactorials() {
		int[] fact = new int[factRange];
		fact[0] = 1;
		for (int i = 1; i < factRange; i++) {
			fact[i] = mulMod(fact[i-1], i);
		}
		return fact;
	}

	public static final int factRange = 1000000;
	public static final int[] fact = precalcFactorials();
	
	public static final int F(int n) {
		return (n < 0) ? 0 : fact[n];
	}
	
	public static final int C(int k, int n) {
		int res = divMod(F(n), mulMod(F(n-k), F(k)));
		return divMod(F(n), mulMod(F(n-k), F(k)));
	} 
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		String s = reader.readLine();
		int len = s.length();
		int[] opnLeft = new int[len], clsRight = new int[len];
		opnLeft[0] = (s.charAt(0) == '(') ? 1 : 0;
		for (int i = 1; i < len; i++) {
			opnLeft[i] = opnLeft[i-1] + ((s.charAt(i) == '(') ? 1 : 0);
		}
		clsRight[len-1] = (s.charAt(len-1) == ')') ? 1 : 0;
		for (int i = len-2; i >= 0; i--) {
			clsRight[i] = clsRight[i+1] + ((s.charAt(i) == ')') ? 1 : 0);
		}
		int res = 0;
		for (int i = 0; i < len; i++) {
			if (s.charAt(i) != '(' || clsRight[i] == 0) {
				continue;
			}
			int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
			res = addMod(res, add);
		}		
		writer.write(Integer.toString(res));
		reader.close();
		writer.close();		
	}
}

Разделите все запросы на блоков. Затем разделите элементы на подвижные (те, которые будут изменяться в данном блоке) и неподвижные. Подумайте, как действовать дальше.

// Thanks to netman for the idea for this wonderful solution :)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <algorithm>

using namespace std;

class SQRTDecomposition {
	private:
		int n, sz;
		vector<int> val;
		vector<int> blocks;
	public:
		inline void add(int v, int delta) {
			val[v] += delta;
			blocks[v / sz] += delta;
		}
		
		inline int sum(int l, int r) {	
			if (l < 0) {
				l = 0;
			}
			if (r >= n) {
				r = n;
			}
			r++;
			int res = 0;
			int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
			for (int i = lBlock; i < rBlock; i++) {
				res += blocks[i];
			}
			int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
			if (lBlockR >= rBlockR) {
				for (int i = l; i < r; i++) {
					res += val[i];
				}
			} else {
				for (int i = l; i < lBlockR; i++) {
					res += val[i];
				}
				for (int i = rBlockR; i < r; i++) {
					res += val[i];
				}
			}
			return res;
		}
		
		inline void clear() {
			val.assign(val.size(), 0);
			blocks.assign(blocks.size(), 0);
		}
		
		SQRTDecomposition(int n, int sz)
			: n(n), sz(sz), val(n, 0), blocks((n + sz - 1) / sz, 0) {
		}
};

struct ToProcess {
	int x, y1, y2, sgn, id;
};

const int BLOCK_SZ_Q = 256;
const int BLOCK_SZ_N = 512;
const int MAX_N = 200000;

int n, q;
vector<ToProcess> sortedL[MAX_N], sortedR[MAX_N];
SQRTDecomposition sum(MAX_N, BLOCK_SZ_N);
int64_t ans[MAX_N], preAns[MAX_N];
pair<int, int> queries[MAX_N];
vector<int> goods;
int p[MAX_N];
bool good[MAX_N];

inline void add(int q, int sgn, int id) {
	if (q-1 >= 0) {
		sortedL[q-1].push_back({q-1, p[q]+1, n-1, sgn, id});
	}
	if (q+1 < n) {
		sortedR[q+1].push_back({q+1, 0, p[q]-1, sgn, id});
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		p[i] = i;
	}
	for (int i = 0; i < q; i++) {
		cin >> queries[i].first >> queries[i].second;
		queries[i].first--; queries[i].second--;
	}
	int64_t cnt = 0;
	for (int i = 0; i < q; i += BLOCK_SZ_Q) {
		int iEnd = min(q, i + BLOCK_SZ_Q);
		for (int j = 0; j < n; j++) {
			good[j] = false;
		}
		for (int j = i; j < iEnd; j++) {
			good[queries[j].first] = true;
			good[queries[j].second] = true;
		}
		goods.clear();
		for (int j = 0; j < n; j++) {
			if (good[j]) {
				goods.push_back(j);
			}
		}
		int64_t goodCnt = 0;
		for (int j = 0; j < n; j++) {
			sortedL[j].clear();
			sortedR[j].clear();
		}
		for (int j = i; j < iEnd; j++) {
			int a = queries[j].first, b = queries[j].second;
			if (a == b) {
				ans[j] += goodCnt;
				continue;
			}
			for (int k = 0; k < (int)goods.size(); k++) {
				int q = goods[k];
				if (q == a || q == b) {
					continue;
				}
				if ((p[q] < p[a] && q > a) ||
				    (p[q] > p[a] && q < a)) {
					goodCnt--;
				}
				if ((p[q] < p[b] && q > b) ||
				    (p[q] > p[b] && q < b)) {
					goodCnt--;
				}
				if ((p[q] < p[b] && q > a) ||
				    (p[q] > p[b] && q < a)) {
					goodCnt++;
				}
				if ((p[q] < p[a] && q > b) ||
				    (p[q] > p[a] && q < b)) {
					goodCnt++;
				}
			}
			if ((a < b && p[a] > p[b]) ||
				(a > b && p[a] < p[b])) {
				goodCnt--;
			} else {
				goodCnt++;
			}
			ans[j] += goodCnt;
			add(a, -1, j);
			add(b, -1, j);
			swap(p[a], p[b]);
			add(a, +1, j);
			add(b, +1, j);
		}
		sum.clear();
		for (int j = 0; j < n; j++) {
			if (!good[j]) {
				sum.add(p[j], 1);
			}
			for (int k = 0; k < (int)sortedL[j].size(); k++) {
				ToProcess &cur = sortedL[j][k];
				int64_t res = sum.sum(cur.y1, cur.y2);
				res *= cur.sgn;
				preAns[cur.id] += res;
			}
		}
		sum.clear();
		for (int j = n-1; j >= 0; j--) {
			if (!good[j]) {
				sum.add(p[j], 1);
			}
			for (int k = 0; k < (int)sortedR[j].size(); k++) {
				ToProcess &cur = sortedR[j][k];
				int64_t res = sum.sum(cur.y1, cur.y2);
				res *= cur.sgn;
				preAns[cur.id] += res;
			}
		}
		for (int j = i; j < iEnd; j++) {
			if (j != i) {
				preAns[j] += preAns[j-1];	
			}
			ans[j] += cnt + preAns[j];
		}
		cnt = ans[iEnd - 1];
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

import java.io.*;
import java.util.*;

public class InversionNSqrtNNoVectors {
	private static final int BLOCK_SZ_Q = 256;
	private static final int BLOCK_SZ_N = 512;
	
	public static class ToProcess {
		public int x, y1, y2, sgn, id;
		
		public void set(int pX, int pY1, int pY2, int pSgn, int pId) {
			x = pX;
			y1 = pY1;
			y2 = pY2;
			sgn = pSgn;
			id = pId;
		}
		
		public ToProcess() {
		}
	}
	
	public static class ToProcessCompareAsc implements Comparator<ToProcess> {
		@Override
		public int compare(ToProcess o1, ToProcess o2) {
			return o1.x - o2.x;
		}
	}
	
	public static class ToProcessCompareDesc implements Comparator<ToProcess> {
		@Override
		public int compare(ToProcess o1, ToProcess o2) {
			return o2.x - o1.x;
		}
	}
	
	static int n, q;
	static int[] p;
	static ToProcess[] queryL, queryR;
	static int queryLCnt, queryRCnt;
	static SQRTDecomposition sum;
	static ToProcessCompareAsc ascCmp = new ToProcessCompareAsc();
	static ToProcessCompareDesc descCmp = new ToProcessCompareDesc();
	
	public static final void add(int q, int sgn, int id) {
		if (q-1 >= 0) {
			queryL[queryLCnt++].set(q-1, p[q]+1, n-1, sgn, id);
		}
		if (q+1 < n) {
			queryR[queryRCnt++].set(q+1, 0, p[q]-1, sgn, id);
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(tokenizer.nextToken());
		q = Integer.parseInt(tokenizer.nextToken());
		int[] qL = new int[q], qR = new int[q];
		long[] ans = new long[q], preAns = new long[q];
		p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
		for (int i = 0; i < q; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			qL[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
			qR[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
		}
		long cnt = 0;
		boolean[] good = new boolean[n];
		int[] goods = new int[n];
		int goodsSize = 0;
		queryL = new ToProcess[4 * BLOCK_SZ_Q]; queryR = new ToProcess[4 * BLOCK_SZ_Q];
		for (int j = 0; j < 4 * BLOCK_SZ_Q; j++) {
			queryL[j] = new ToProcess();
			queryR[j] = new ToProcess();
		}
		SQRTDecomposition sum = new SQRTDecomposition(n, BLOCK_SZ_N);
		for (int i = 0; i < q; i += BLOCK_SZ_Q) {
			int iEnd = Math.min(q, i + BLOCK_SZ_Q);
			Arrays.fill(good, false);
			for (int j = i; j < iEnd; j++) {
				good[qL[j]] = true;
				good[qR[j]] = true;
			}
			goodsSize = 0;
			for (int j = 0; j < n; j++) {
				if (good[j]) {
					goods[goodsSize++] = j;
				}
			}
			long goodCnt = 0;
			queryLCnt = 0;
			queryRCnt = 0;
			for (int j = i; j < iEnd; j++) {
				int a = qL[j], b = qR[j];
				if (a == b) {
					ans[j] += goodCnt;
					continue;
				}
				for (int k = 0; k < goodsSize; k++) {
					int q = goods[k];
					if (q == a || q == b) {
						continue;
					}
					if ((p[q] < p[a] && q > a) ||
						(p[q] > p[a] && q < a)) {
						goodCnt--;
					}
					if ((p[q] < p[b] && q > b) ||
						(p[q] > p[b] && q < b)) {
						goodCnt--;
					}
					if ((p[q] < p[b] && q > a) ||
						(p[q] > p[b] && q < a)) {
						goodCnt++;
					}
					if ((p[q] < p[a] && q > b) ||
						(p[q] > p[a] && q < b)) {
						goodCnt++;
					}
				}
				if ((a < b && p[a] > p[b]) ||
					(a > b && p[a] < p[b])) {
					goodCnt--;
				} else {
					goodCnt++;
				}
				ans[j] += goodCnt;
				add(a, -1, j);
				add(b, -1, j);
				int tmp = p[a];
				p[a] = p[b];
				p[b] = tmp;
				add(a, +1, j);
				add(b, +1, j);
			}
			sum.clear();
			Arrays.sort(queryL, 0, queryLCnt, ascCmp);
			int curL = 0;
			for (int j = 0; j < n; j++) {
				if (!good[j]) {
					sum.add(p[j], 1);
				}
				for (; curL < queryLCnt; curL++) {
					ToProcess cur = queryL[curL];
					if (cur.x != j) {
						break;
					}
					int res = sum.sum(cur.y1, cur.y2);
					res *= cur.sgn;
					preAns[cur.id] += res;
				}
			}
			sum.clear();
			Arrays.sort(queryR, 0, queryRCnt, descCmp);
			int curR = 0;
			for (int j = n-1; j >= 0; j--) {
				if (!good[j]) {
					sum.add(p[j], 1);
				}
				for (; curR < queryRCnt; curR++) {
					ToProcess cur = queryR[curR];
					if (cur.x != j) {
						break;
					}
					int res = sum.sum(cur.y1, cur.y2);
					res *= cur.sgn;
					preAns[cur.id] += res;
				}
			}
			for (int j = i; j < iEnd; j++) {
				if (j != i) {
					preAns[j] += preAns[j-1];	
				}
				ans[j] += cnt + preAns[j];
			}
			cnt = ans[iEnd - 1];
		}
		for (int i = 0; i < q; i++) {
			writer.write(Long.toString(ans[i]));
			writer.newLine();
		}
		reader.close();
		writer.close();
	}
}

class SQRTDecomposition {
	private int n;
	private int sz;
	private int[] val;
	private int[] blocks;
	
	public final void add(int v, int delta) {
		val[v] += delta;
		blocks[v / sz] += delta;
	}
		
	public final int sum(int l, int r) {	
		if (l < 0) {
			l = 0;
		}
		if (r >= n) {
			r = n;
		}
		r++;
		int res = 0;
		int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
		for (int i = lBlock; i < rBlock; i++) {
			res += blocks[i];
		}
		int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
		if (lBlockR >= rBlockR) {
			for (int i = l; i < r; i++) {
				res += val[i];
			}
		} else {
			for (int i = l; i < lBlockR; i++) {
				res += val[i];
			}
			for (int i = rBlockR; i < r; i++) {
				res += val[i];
			}
		}
		return res;
	}
	
	public void clear() {
		Arrays.fill(val, 0);
		Arrays.fill(blocks, 0);
	}
		
	SQRTDecomposition(int pN, int pSz) {
		n = pN;
		sz = pSz;
		val = new int[n];
		blocks = new int[(n + sz - 1) / sz];
	}
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <iomanip>

#define sqr(a) (a)*(a)
#define all(a) (a).begin(), (a).end()
using namespace std;

template <typename T>
T next_int() {
    T ans = 0, t = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ') ;
    if(ch == '-') {
        t = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        ans = ans * 10 + (ch - '0');
        ch = getchar();
    }
    return ans * t;
}

string next_token() {
    char ch;
    string ans = "";
    do { ch = getchar(); } while(ch <= ' ') ;
    while(ch >= ' ') {
        ans += ch;
        ch = getchar();
    }
    return ans;
}

const long long INF = (long long)1e18 + 227 + 1;
const int INFINT = (int)1e9 + 227 + 1;
const int MAXN = (int)2e5 + 227 + 1;
const int MOD = (int)1e9 + 7;
const long double EPS = 1e-9;

long long bin_pow(long long n, long long k) {
    if(!k) return 1;
    long long ans = bin_pow(n, k / 2);
    ans = ans * ans % MOD;
    if(k % 2) ans = ans * n % MOD;
    return ans;
}

struct tree {
    int size_block;
    int len; 
 
    tree(int len) : len(len) {
        size_block = sqrt(len);
 
        kek.resize(len / size_block + 1, vector<int>(size_block, 0));
 
        pr_block.resize(len / size_block + 1, 0);
    }
 
    vector<int> pr_block;
    vector<vector<int> > kek;
 
    void inc(int pos, int num) {
        int x = pos / size_block;
 
        for(int i = pos % size_block; i < size_block; i++) {
            kek[x][i] += num;
        }
 
        for(int i = 0; i <= len / size_block; i++)
            if(i == 0) {
                pr_block[i] = kek[i][size_block - 1];
            } else {
                pr_block[i] = pr_block[i - 1] + kek[i][size_block - 1]; 
            }
    }
 
    int f(int a) {
        return a / size_block;
    }
 
    long long get(vector<int> &a, int l, int r, bool ok = 1) {
        if(ok == 1) {
            l %= size_block;
            r %= size_block;
        }
 
        return a[r] - (l ? a[l - 1] : 0);
    }
 
    int get(int l, int r) {
        if(l > r) return 0;

        r = min(r, len);
  
        if(f(l) == f(r))
            return get(kek[f(l)], l, r);
     
        int ans = 0;
 
        if(l % size_block) {
            ans += get(kek[f(l)], l, size_block - 1);
 
            l += size_block - l % size_block;
        }
 
        if(r % size_block != size_block - 1) {
            ans += get(kek[f(r)], 0, r);
 
            r -= r % size_block + 1;
        }
 
        ans += get(pr_block, f(l), f(r), 0);
 
        return ans;
    }
 
    int get_pref(int p) {
        return get(1, p - 1);
    }

    int get_suff(int p) {
        return get(p + 1, len);
    }
} ;

struct mda {
    vector<int> a;
    vector<tree> t;
    int len, sz;
    long long ans;

    mda(int len) : len(len) {
        sz = 2000;
        ans = 0;

        a.resize(len + 1);
        for(int i = 1; i <= len; i++)
            a[i] = i;

        for(int i = 1; i <= len; i += sz) {
            t.push_back(tree(len));
            for(int j = i; j < i + sz && j <= len; j++)
                add(j, j);
        }
    }

    int get_pref(int L, int R, int k) {
        int ans = 0;

        for(int l = 1; l <= R; l += sz) {
            int r = l + sz - 1;

            if(r < L || l > R) continue;

            if(L <= l && r <= R)
                ans += t[(l - 1) / sz].get_pref(k);
            else
                for(int i = max(l, L); i <= min(r, R); i++) 
                    ans += (a[i] < k);
        }

        return ans;
    }

    int get_suff(int L, int R, int k) {
        int ans = 0;

        for(int l = 1; l <= R; l += sz) {
            int r = l + sz - 1;

            if(r < L || l > R) continue;

            if(L <= l && r <= R)
                ans += t[(l - 1) / sz].get_suff(k);
            else
                for(int i = max(l, L); i <= min(r, R); i++) 
                    ans += (a[i] > k);
        }

        return ans;
    }

    void del(int p, int k) {
        p = (p - 1) / sz;
        t[p].inc(k, -1);
    }

    void add(int p, int k) {
        p = (p - 1) / sz;
        t[p].inc(k, 1);
    }

    void sw(int i, int j) {
        if(i == j) return;
        if(i > j) swap(i, j);

        ans -= get_pref(i, j, a[i]);
        ans -= get_suff(i, j, a[j]);

        if(a[i] > a[j]) ans++;

        del(i, a[i]);
        del(j, a[j]);
        swap(a[i], a[j]);
        add(i, a[i]);
        add(j, a[j]);

        ans += get_pref(i, j, a[i]);
        ans += get_suff(i, j, a[j]);

        if(a[i] > a[j]) ans--;
    }
} ;

int main() {
    // freopen(".in", "r", stdin);

    int n, m; cin >> n >> m;

    mda t(n);

    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;

        t.sw(x, y);
        
        cout << t.ans << "\n";
    }
}

import java.io.*;
import java.util.*;

public class NsqrtNlogNnetman implements Runnable {
    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
        InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in), 32768);
            tokenizer = null;
        }
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static class Fenwick {
        int[] ft;
        Fenwick(int n) {
            ft = new int[n];
        }
        void add(int r, int val) {
            while (r < ft.length) {
                ft[r] += val;
                r |= r + 1;
            }
        }
        int sum(int r) {
            int res = 0;
            while (r >= 0) {
                res += ft[r];
                r = (r & (r + 1)) - 1;
            }
            return res;
        }
        void clear() {
            Arrays.fill(ft, 0);
        }
    }

    static class Query {
        int x, bound, sign, id;
        Query(int x, int bound, int sign, int id) {
            this.x = x;
            this.bound = bound;
            this.sign = sign;
            this.id = id;
        }
    }

    static void getOnPrefSmaller(List<Query> qrs, int r, int y, int id, int sign) {
        qrs.add(new Query(r, y, sign, id));
    }

    static void getOnPrefBetween(List<Query> qrs, int r, int x, int y, int id, int sign) {
        getOnPrefSmaller(qrs, r, y, id, sign);
        getOnPrefSmaller(qrs, r, x, id, -sign);
    }

    static void getOnSegmentBetween(List<Query> qrs, int l, int r, int x, int y, int id, int sign) {
        if (x > y) return;
        getOnPrefBetween(qrs, r, x, y, id, sign);
        getOnPrefBetween(qrs, l, x, y, id, -sign);
    }

    @Override
    public void run() {

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int q = in.nextInt();

        int[] l = new int[q];
        int[] r = new int[q];

        for (int i = 0; i < q; i++) {
            l[i] = in.nextInt() - 1;
            r[i] = in.nextInt() - 1;
        }

        int[] perm = new int[n];

        for (int i = 0; i < n; i++) {
            perm[i] = n - i - 1;
        }

        final int BLOCK = 300;

        long inv = 0L;

        boolean[] isInteresting = new boolean[n];

        long[] add = new long[q];

        Fenwick f = new Fenwick(n);

        for (int i = 0; i < q; i += BLOCK) {
            int from = i, to = Math.min(i + BLOCK, q) - 1;
            List<Integer> lst = new ArrayList<>();
            for (int j = from; j <= to; j++) {
                lst.add(l[j]);
                lst.add(r[j]);
            }
            lst.sort(Integer::compareTo);
            lst = new ArrayList<>(new HashSet<>(lst));
            int[] interestingPositions = lst.stream().mapToInt(x -> x).toArray();
            for (int pos : interestingPositions) {
                isInteresting[pos] = true;
            }
            List<Query> qrs = new ArrayList<>();
            for (int j = from; j <= to; j++) {
                if (l[j] == r[j]) continue;
                if (l[j] > r[j]) {
                    int tmp = l[j];
                    l[j] = r[j];
                    r[j] = tmp;
                }
                if (perm[l[j]] < perm[r[j]]) {
                    getOnSegmentBetween(qrs, l[j], r[j], perm[l[j]], perm[r[j]], j,-1);
                    int leftValue = perm[l[j]];
                    int rightValue = perm[r[j]];
                    for (int pos : interestingPositions) {
                        if (pos > l[j] && pos < r[j] && perm[pos] > leftValue && perm[pos] < rightValue) {
                            add[j] -= 2;
                        }
                    }
                    add[j]--;
                } else {
                    getOnSegmentBetween(qrs, l[j], r[j], perm[r[j]], perm[l[j]], j,1);
                    int leftValue = perm[l[j]];
                    int rightValue = perm[r[j]];
                    for (int pos : interestingPositions) {
                        if (pos > l[j] && pos < r[j] && perm[pos] > rightValue && perm[pos] < leftValue) {
                            add[j] += 2;
                        }
                    }
                    add[j]++;
                }
                int tmp = perm[l[j]];
                perm[l[j]] = perm[r[j]];
                perm[r[j]] = tmp;
            }
            qrs.sort(Comparator.comparingInt(a -> -a.x));

            f.clear();
            for (int pos = 0; pos < n; pos++) {
                if (!isInteresting[pos]) {
                    f.add(perm[pos], 1);
                }
                while (!qrs.isEmpty() && qrs.get(qrs.size() - 1).x == pos) {
                    Query t = qrs.get(qrs.size() - 1);
                    qrs.remove(qrs.size() - 1);
                    add[t.id] += 2 * t.sign * f.sum(t.bound);
                }
            }
            for (int j = from; j <= to; j++) {
                inv += add[j];
                out.println(inv);
            }
            for (int pos : interestingPositions) {
                isInteresting[pos] = false;
            }
        }



        out.close();
    }

    public static void main(String[] args) {
        new Thread(null, new NsqrtNlogNnetman(), "1", 1L << 28).run();
    }
}

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int n; cin >> n;
	string s; cin >> s;
	int k_a = 0, k_d = 0;
	for (int i = 0; i < n; i++)
		if (s[i] == 'A') k_a++; else k_d++;
	if (k_a > k_d) cout << "Anton" << endl;
	if (k_a < k_d) cout << "Danik" << endl;
	if (k_a == k_d) cout << "Friendship" << endl;
	return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int k2, k3, k5, k6;
	cin >> k2 >> k3 >> k5 >> k6;
	int n256 = min(k2, min(k5, k6));
	int n32 = min(k3, k2 - n256);
	cout << 32 * n32 + 256 * n256 << endl;
	return 0;
}

#include <iostream>

using namespace std;

const int max_n = 1000000;

int n, m, k;
int x, s;
int a[max_n], b[max_n], c[max_n], d[max_n];

inline int max_complete(int money_left)
{
	int l = 0, r = k;
	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (d[m] <= money_left) l = m; else r = m-1;
	}
	return c[l];
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	cin >> x >> s;
	a[0] = x;
	b[0] = 0;
	c[0] = 0;
	d[0] = 0;
	for (int i = 1; i <= m; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	for (int i = 1; i <= k; i++) cin >> c[i];
	for (int i = 1; i <= k; i++) cin >> d[i];
	long long ans = 1LL * n * x;
	for (int i = 0; i <= m; i++)
	{
		int money_left = s - b[i];
		if (money_left < 0) continue;
		ans = min(ans, 1LL * (n - max_complete(money_left)) * a[i]);
	}
	cout << ans << endl;
	return 0;
}

#include <cstdio>
#include <algorithm>

using namespace std;

inline char in_char()
{
	char c = '\0';
	while (c <= ' ')
		c = getchar();
	return c;
}

inline int in_int()
{
	int n;
	scanf("%d", &n);
	return n;
}

struct figurine
{
	char kind;
	int x, y;
};

int n;
int x0, y0;
figurine nearest[8];

inline int dist(int x1, int y1, int x2, int y2)
{
	return max(abs(x1 - x2), abs(y1 - y2));
}

inline void upd_nearest(figurine& was, const figurine& cur)
{
	if (was.kind == '?' ||
	    dist(x0, y0, cur.x, cur.y) < dist(x0, y0, was.x, was.y))
	was = cur;
}

inline int get_direction(const figurine& cur)
{
	// vertical
	if (cur.x == x0 && cur.y < y0) return 0;
	if (cur.x == x0 && cur.y > y0) return 1;
	// horizontal
	if (cur.y == y0 && cur.x < x0) return 2;
	if (cur.y == y0 && cur.x > x0) return 3;
	// diagonal 1
	if ((cur.y - y0) == (cur.x - x0) && cur.x < x0) return 4;
	if ((cur.y - y0) == (cur.x - x0) && cur.x > x0) return 5;
	// diagonal 2
	if ((cur.y - y0) == (x0 - cur.x) && cur.y < y0) return 6;
	if ((cur.y - y0) == (x0 - cur.x) && cur.y > y0) return 7;
	// the piece doesn't lie on any of the eight directions
	return -1;
}

int main()
{
	n = in_int();
	x0 = in_int(); y0 = in_int();
	for (int i = 0; i < 8; i++)
		nearest[i].kind = '?';
	// read and update nearest
	for (int i = 0; i < n; i++)
	{
		figurine cur;
		cur.kind = in_char(); cur.x = in_int(); cur.y = in_int();
		int dir = get_direction(cur);
		if (dir >= 0)
			upd_nearest(nearest[dir], cur);
	}
	bool ans = false;
	// check verticals and horizontals
	for (int i = 0; i < 4; i++)
		if (nearest[i].kind == 'R' || nearest[i].kind == 'Q')
			ans = true;
	// check diagonals
	for (int i = 4; i < 8; i++)
		if (nearest[i].kind == 'B' || nearest[i].kind == 'Q')
			ans = true;
	// output
	puts(ans ? "YES" : "NO");
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector <int> color;
vector < vector <int> > g;
vector <char> used;
vector <int> comp;
int n1;
vector < vector <int> > g1;
vector <int> dp;
int ans = 0;

void dfs1(int v, int col, int cmp)
{
    if (used[v]) return;
    if (color[v] != col) return;
    used[v] = true;
    comp[v] = cmp;
    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        dfs1(to, col, cmp);
    }
}

void dfs2(int v, int p = -1)
{
    int mx1 = 0, mx2 = 0;
    for (int i = 0; i < g1[v].size(); i++)
    {
        int to = g1[v][i];
        if (to == p) continue;
        dfs2(to, v);
        int val = dp[to] + 1;
        mx2 = max(mx2, val);
        if (mx1 < mx2) swap(mx1, mx2);
    }
    dp[v] = mx1;
    ans = max(ans, mx1 + mx2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    color.resize(n);
    g.resize(n);
    comp.resize(n);
    used.assign(n, false);
    for (int i = 0; i < n; i++) cin >> color[i];
    for (int i = 1; i < n; i++)
    {
        int a, b; cin >> a >> b; a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < n; i++)
        if (!used[i])
            dfs1(i, color[i], n1++);
    g1.resize(n1);
    dp.resize(n1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < g[i].size(); j++)
        {
            int to = g[i][j];
            if (comp[i] != comp[to])
                g1[comp[i]].push_back(comp[to]);
        }
    dfs2(0);
    cout << (ans + 1) / 2 << endl;
    return 0;
}

#include <iostream>

using namespace std;

const int max_n = 300000;

int n;
int b[max_n];
int c[max_n];
int a[max_n];
int d[max_n];
int b1[max_n];
int c1[max_n];
int bits[31][max_n];
int kbit[31];

int main()
{
	// input
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> b[i];
	for (int i = 0; i < n; i++) cin >> c[i];
	for (int i = 0; i < n; i++) d[i] = b[i] + c[i];

	// searching for answer
	long long sum = 0;
	for (int i = 0; i < n; i++) sum += d[i];
	sum /= (2 * n);

	for (int i = 0; i < n; i++) a[i] = (d[i] - sum) / n;

	// checking the answer
    for (int i = 0; i < n; i++)
        if (a[i] < 0)
        {
            cout << -1 << endl;
            return 0;
        }
	
	for (int i = 0; i < 31; i++)
		for (int j = 0; j < n; j++)
			if ((a[j] & (1LL << i)) == 0)
				bits[i][j] = 0;
			else
				bits[i][j] = 1;
	for (int i = 0; i < 31; i++)
	{
		kbit[i] = 0;
		for (int j = 0; j < n; j++)
			kbit[i] += bits[i][j];
	}

	for (int i = 0; i < n; i++) b1[i] = 0;
	for (int i = 0; i < n; i++) c1[i] = 0;

	for (int i = 0; i < 31; i++)
		for (int j = 0; j < n; j++)
		{
			int bbase = bits[i][j] ? kbit[i] : 0;
			int cbase = bits[i][j] ? n : kbit[i];
			b1[j] += bbase << i;
			c1[j] += cbase << i;
		} 

	for (int i = 0; i < n; i++)
		if (b1[i] != b[i] || c1[i] != c[i])
		{
			cout << -1 << endl;
			return 0;
		}	

	// output
	for (int i = 0; i < n; i++) cout << a[i] << " ";
	cout << endl;
	return 0;
}