이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
#include<chrono>
#include<random>
#define ll long long
#define DB double
#define pii pair<int, int>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF (ll)(1e9+5)
#define MOD (ll)(998244353)
#define endl "\n"
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define N 200005
#define M 200005
using namespace std;
int sum[N];
int n, m;
int used[N];
pair<int, int> find(int maxn) {
int l = n+1, r = 1;
FOR(i, 1, n+1) {
if (sum[i] >= maxn - 1) {
l = min(l, i);
r = max(r, i);
}
}
return mp(l, r);
}
int main() {
AC;
cin >> n >> m;
int maxn = 0;
ll ans = 0;
vector<pair<int, int> > v;
FOR(i, 0, m) {
int a, b, c; cin >> a >> b >> c;
if (a > b) swap(a, b);
//ans += c / 2;
//c %= 2;
//if (!c) continue;
v.pb(mp(a, b));
FOR(j, a, b) {
sum[j]++;
maxn = max(maxn, sum[j]);
}
}
int l, r;
while (1) {
pair<int, int> tmp = find(maxn);
l = tmp.F; r = tmp.S;
bool ok = 0;
FOR(i, 0, v.size()) {
if (!used[i]){
if (v[i].F <= l && v[i].S > r) {
ok = 1;
used[i] = 1;
maxn--;
FOR(j, 1, n+1) {
if (v[i].F <= j && j < v[i].S) sum[j]--;
else sum[j]++;
}
break;
}
} else {
bool ck = 1;
FOR(j, v[i].F, v[i].S) {
if (sum[j] >= maxn - 1) {
ck = 0;
break;
}
}
if (ck) {
ok = 1;
used[i] = 0;
maxn--;
FOR(j, 1, n+1) {
if (v[i].F <= j && j < v[i].S) sum[j]++;
else sum[j]--;
}
break;
}
}
}
if (!ok) break;
}
cout << ans + maxn << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |