Районная олимпиада 2019-2020 информатика

Задача C. Ресторан

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

В ресторане есть $n$ официантов. Они пронумерованы от $1$-го до $n$. На столе стоят $m$ стаканов. Они пронумерованы от $1$-го до $m$. Изначально все стаканы пустые. Каждый официант должен налить напиток в некоторые стаканы. $i$-й официант должен налить в стаканы с номерами от $l_i$ до $r_i$ по $x_i$ миллилитров напитка. Какой-то официант проспал и забыл сделать это. Все остальные кроме него выполнили задание. Вам дано количество миллилитров напитка в каждом стакане. Нужно найти список, тех официантов, кто возможно проспал.

Формат входного файла

В первой строке дается два целых числа $n$ и $m$ $(1 <= n, m <= 10^5)$ — количество официантов и количество стаканов. В следующих $n$ строках заданы по три целых числа $l_i$, $r_i$ и $x_i$ $(1 <= l_i <= r_i <= m$, $1 <= x_i <= 10^3)$. В следующей строке заданы $m$ целых числа $a_1$, $a_2$, $\dots$, $a_m$, где $a_i$ обозначает количество миллилитров напитка в $i$-м стакане.

Формат выходного файла

Выведите номера в отсортированном порядке, тех официантов, кто возможно проспал.

Система оценки

Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= n, m <= 100$. Тесты с номерами 1-2.
2. $1 <= n, m <= 3000$. Тесты с номерами 3-5.
3. $1 <= n, m <= 10^5$. Тесты с номерами 6-10.

Пример:

Вход

5 4
1 3 2
2 4 3
1 3 2
3 4 1
3 3 1
2 5 7 4

Ответ

1 3

( Aibar Kuanyshbay )

Комментарий/решение

С новым годом. Не проходит по времяни в 6 том тесте. Буду благодарен, если найдете другие варианты решение. :)

показать/скрыть код

#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> a(m);
    vector<vector<int> > b(n,vector<int>(m));
    fill(a.begin(),a.end(),0);
    for(int i=0;i<n;i++){
        int l,r,x;
        cin>>l>>r>>x;
        for(int j=l-1;j<r;j++) {
            a[j]+=x;
            b[i][j]=x;
        }
    }
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        a[i]=a[i]-x;
    }
    for(int i=0;i<n;i++) {
        int t=0;
        for(int j=0;j<m;j++){
            b[i][j]=a[j]-b[i][j];
            if(b[i][j]==0) t++;
        }
        if(t==m) cout<<i+1<<" ";
    }
    return 0;
}

В своем решение вы полностью проходите по отрезку [l, r]. Это решение будет работать но так как вы делаете это 10^5 раз итоговая асимптотика выходит O(nm), что очень медленно. Задача решается с помощью дерева отрезков или же так как задача без обновлений, то есть офлайн можно итоговый массив получить вот так:

При каждом считывании l, r, x в дополнительном массиве на индексе l добавьте x, в индексе r + 1 отнимите x. Затем поступите префикс сумму по этому массиву и это будет итоговый массив.

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 2e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n, m, a[N], b[N], cur[N], l, r, sz;
pair < pii, int > x[N];
vi ans;

int main () {
    start
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> x[i].F.F >> x[i].F.S >> x[i].S;
        cur[x[i].F.F] += x[i].S;
        cur[x[i].F.S + 1] -= x[i].S;
    }
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    int kol = 0;
    for(int i = 1; i <= m; i++) {
        kol += cur[i];
        b[i] += kol;
    }
    for(int i = 1; i <= m; i++) {
        if(b[i] != a[i]) {
            if(l == 0) l = i;
            r = i;
            sz = b[i] - a[i];
        }
        else if(l != 0) break;
    }
    pair < pii, int > check = mp(mp(l, r), sz);
    for(int i = 1; i <= n; i++) {
        if(x[i] == check) ans.pb(i);
    }
    for(auto i : ans) {
        cout << i << ' ';
    }
    return 0;
}

n, m = input().split()

n, m = int(n), int(m)

lrx = [[]for i in range(n)]

for i in range(n):

lrx[i] = input().split()

for j in range(3):

lrx[i][j] = int(lrx[i][j])

a= input().split()

for i in range(len(a)):

a[i] = int(a[i])

a_full = [0]*m

for i in range(n):

l=lrx[i][0]

r=lrx[i][1]

x=lrx[i][2]

for j in range(l-1,r):

a_full[j]+=x

mistake = [0]*3

l = float('inf')

for i in range(m):

if a[i] != a_full[i]:

mistake[2] = a_full[i]-a[i]

if i<l:

mistake[0] = l = i+1

mistake[1]= i+1

maybe=[]

for i in range(n):

if lrx[i][0] == mistake[0] and lrx[i][1] == mistake[1] and lrx [i][2] == mistake[2]:

maybe.append(i+1)

for i in maybe:

print(i)

...

показать/скрыть код

#include <bits/stdc++.h>
// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
// #pragma comment(linker, "/stack:200000000")
using namespace std;
#define all(v) v.begin(),v.end()
#define ll long long
#define sz(s) (int)s.size()
#define F first
#define S second
#define pb push_back
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define go ios_base::sync_with_stdio(false);cin.tie(NULL);
template<class T> bool mi(T& a,const T& b) {
  return (b<a ? a=b, 1:0);
}
template<class T> bool umax(T& a,const T& b) {
  return (a<b ? a=b,1:0);
}
template<class A> void read(vector<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vector<A>& x) {
	for(auto & a : x)read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	for(auto & a : x)read(a);
}
ll binpow (ll a, ll n) {
	ll res=1;
	while (n) {
		if (n&1)res*=a;
		a*=a;
		n>>=1;
	}
	return res;
}
const ll N=1e5+12;
ll a[N];
void solve() {
	ll n, m;
	cin>>n>>m;
	vector<pair<pair<ll, ll>, ll > > v; 
	for(int i=0; i<n; i++) {
		ll l, r;
		cin>>l>>r;
		ll x;
		cin>>x;
		v.pb({{l, r}, x});
		a[l]+=x;
		a[r+1]-=x;
	}
	for(int i=1; i<=m; i++) {
		a[i]=a[i]+a[i-1];
	}
	ll b[m+7];
	ll l1=-1, r1=-1;
	bool ok=0;
	for(int i=1; i<=m; i++) {
		cin>>b[i];
		if (b[i]!=a[i] && !ok) {
			l1=i;
			ok=1;
		}
		if (b[i]==a[i] && ok) {
			r1=i-1;
			break;
		}
	}
	ll x1=a[l1]-b[l1];
	for(int i=0; i<sz(v); i++) {
		if (l1==v[i].F.F && r1==v[i].F.S && x1==v[i].S) {
			cout << i+1 << ' ';
		}
	}
}
signed main() {
	go;
	int t=1;
	//cin>>t;
	while (t--)solve();
}
/*
9 0
6 8 2 9 1 8 10 8 6

*/