Submission #1094544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094544		I_am_Polish_Girl	Gift Exchange (JOI24_ho_t4)	C++14	100 / 100	1277 ms	136920 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimization ("unroll-loops")

#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <bitset>
#include <cmath>

#define int long long

using namespace std;


int log_ = 3;
int inf = 2000000007000000007;
int mod = 1000000007;

int p = 501;

struct segment_tree
{
	struct value
	{
		int min;
		int pluss;
	};

	vector<value> tree;
	int size;
	void build(int n)
	{
		size = 1;
		while (size < n)
		{
			size *= 2;
		}
		tree.resize(2 * size, { 0 , -1 });
	}
	void propagate(int ind)
	{
		if (tree[ind].pluss == -1)
			return;
		tree[ind * 2 + 1].pluss = tree[ind].pluss;
		tree[ind * 2 + 2].pluss = tree[ind].pluss;
		tree[ind * 2 + 1].min = tree[ind].pluss;
		tree[ind * 2 + 2].min = tree[ind].pluss;
		tree[ind].pluss = -1;
	}
	void modify(int l, int r, int ind, int lx, int rx, int v)
	{
		if (r <= lx)
			return;
		if (rx <= l)
			return;
		if (r - l == 1)
		{
			tree[ind].min = v;
			tree[ind].pluss = v;
			return;
		}
		if ((lx <= l) and (r <= rx))
		{
			tree[ind].min = v;
			tree[ind].pluss = v;
			return;
		}

		propagate(ind);
		int m = (r + l) / 2;
		modify(l, m, ind * 2 + 1, lx, rx, v);
		modify(m, r, ind * 2 + 2, lx, rx, v);
		if (tree[ind].pluss == -1)
			tree[ind].min = min(tree[ind * 2 + 1].min, tree[ind * 2 + 2].min);
		else
			tree[ind].min = tree[ind].pluss;
	}
	void modify(int lx, int rx, int v)
	{
		modify(0, size, 0, lx, rx, v);
	}

	int get(int l, int r, int ind, int lx, int rx, int first)
	{
		if (r <= lx)
			return inf;
		if (rx <= l)
			return inf;
		if ((lx <= l) and (r <= rx))
		{
			if (first == -1)
			{
				return tree[ind].min;
			}
			else
			{
				return first;
			}
		}
		if ((first == -1) and (tree[ind].pluss != -1))
		{
			first = tree[ind].pluss;
		}
		int m = (r + l) / 2;
		int g1 = get(l, m, ind * 2 + 1, lx, rx, first);
		int g2 = get(m, r, ind * 2 + 2, lx, rx, first);
		return min(g1, g2);
	}
	int get(int lx, int rx)
	{
		return get(0, size, 0, lx, rx, -1);
	}
};



struct segment_tree2
{
	vector <pair <long long , long long >> tree;
	int size;
	int size2;
	void init(int n)
	{
		size2 = n;
		size = 1;
		while (size < n)
			size *= 2;
		tree.resize(size * 2, { 0 , 0 });
	}

	void build(int l, int r, int ind)
	{
		if (r - l == 1)
		{
			if (l < size2)
				tree[ind].first = 0;
			return;
		}
		int m = (r + l) / 2;
		build(l, m, ind * 2 + 1);
		build(m, r, ind * 2 + 2);
		tree[ind].first = tree[ind * 2 + 1].first + tree[ind * 2 + 2].first;
	}

	void build(int n)
	{
		init(n);
		//build(0, size, 0);
	}
	/*
	void push(int ind)
	{
		if (tree[ind] != -1)
		{
			tree[ind * 2 + 1] = tree[ind];
			tree[ind * 2 + 2] = tree[ind];
			tree[ind] = -1;
		}
	}*/
	void modified(int l, int r, int ind, int lx, int rx, long long v)
	{
		if (r <= lx)
			return;
		if (rx <= l)
			return;

		if (r - l == 1)
		{
			tree[ind].second += v;

			tree[ind].first += v * (r - l);
			return;
		}

		if ((lx <= l) and (r <= rx))
		{
			tree[ind].second += v;

			tree[ind].first += v * (r - l);
			return;
		}
		int m = (r + l) / 2;
		modified(l, m, ind * 2 + 1, lx, rx, v);
		modified(m, r, ind * 2 + 2, lx, rx, v);
		tree[ind].first = (tree[ind * 2 + 1].first + tree[ind * 2 + 2].first) + tree[ind].second * (r - l);
	}
	void modified(int lx, int rx, int v)
	{
		modified(0, size, 0, lx, rx, v);
	}

	long long get(int l, int r, int ind, int lx, int rx, long long sum)
	{
		if (r <= lx)
			return 0;
		if (rx <= l)
			return 0;

		if (r - l == 1)
		{
			return tree[ind].first + sum * (r - l);
		}

		if ((lx <= l) and (r <= rx))
		{
			return tree[ind].first + sum * (r - l);
		}
		sum += tree[ind].second;

		int m = (r + l) / 2;
		int g1 = get(l, m, ind * 2 + 1, lx, rx, sum);
		int g2 = get(m, r, ind * 2 + 2, lx, rx, sum);
		return g1 + g2;
	}
	long long get(int l, int r)
	{
		return get(0, size, 0, l, r, 0);
	}
};



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector <int> a(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector <int> b(n);

    for (int i = 0; i < n; i++)
        cin >> b[i];

    vector <int> l(n , -1);
    vector <int> r(n , n);

	segment_tree st;

	st.build(2 * n + 10);

	st.modify(0, 2 * n + 10, n);
    
	for (int i = n - 1; i >= 0; i--)
	{
		r[i] = st.get(b[i], a[i]+1);

		st.modify(b[i], a[i] + 1, i);
	}

	st.modify(0, 2 * n + 10, 10000);

	for (int i = 0; i < n; i++)
	{
		l[i] = st.get(b[i], a[i] + 1);

		l[i] *= -1;
		l[i] -= 10;

		st.modify(b[i], a[i] + 1, -(i+ 10));

		if (l[i] < 0)
			l[i] = -1;
	}


    vector <vector <pair <pair <int , int> , int>>> lx(n+1);
    
	for (int i = 0; i < n; i++)
	{
		lx[l[i] + 1].push_back({ {i , r[i] - 1} , 1 });

		lx[i+1].push_back({ {i , r[i] - 1} , -1 });
    }
    
    vector <vector <pair <int , int>>> q(n);

    int q_;
    cin >> q_;

    for (int i = 0 ; i < q_ ; i++)
    {
        int l, r;
        cin >> l >> r;

        l--;
        r--;

        q[l].push_back({ r , i });
    }


    vector <bool> ans(q_);


	segment_tree2 st2;

	st2.init(n + 10);

    for (int i = 0; i < n; i++)
    {
		for (int j = 0; j < lx[i].size(); j++)
		{
			if (lx[i][j].second == 1)
				st2.modified(lx[i][j].first.first, lx[i][j].first.second+1, 1);
			else
				st2.modified(lx[i][j].first.first, lx[i][j].first.second+1, -1);
		}

        for (int j = 0; j < q[i].size(); j++)
        {
            int r = q[i][j].first;
            int ind = q[i][j].second;

            if (st2.get(r , r+1) > 0)
                ans[ind] = 0;
            else
                ans[ind] = 1;
        }
    }

    for (int i = 0; i < q_ ; i++)
    { 
        if (ans[i] == 1)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

Compilation message (stderr)

Main.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
Main.cpp: In function 'int main()':
Main.cpp:320:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  320 |   for (int j = 0; j < lx[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~
Main.cpp:328:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  328 |         for (int j = 0; j < q[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 12 / 12